Persi Diaconis

Laurent Miclo

On characterizations of Metropolis type algorithms in continuous time

Keywords: Metropolis algorithms, finite jump Markov processes, compact manifold-valued diffusion processes, relative entropy minimizations, ϕ-relative entropies, discrepancies on sets of Markov generators, martingale problems, general Girsanov transformations 60J22 secondary: 60J25, 60J27, 60J57, 94A17, 58J65

In the continuous time framework, a new definition is proposed for the Metropolis algorithm ( X t ) t≥0 associated to an a priori given exploratory Markov process (X t ) t≥0 and to a tarjet probability distribution π. It should be the minimizer for the relative entropy of the trajectorial law of ( X t ) t∈[0,T ] with respect to the law of (X t ) t∈[0,T ] , when both processes start with π as initial law and when π is assumed to be reversible for ( X t ) t≥0 . This definition doesn't depend on the time horizon T > 0 and the corresponding minimizing process is not difficult to describe. Even if this procedure can be made general, the details were only worked out in situation of finite jump processes and of compact manifold-valued diffusion processes (a sketch is also given for Markov processes admitting both a diffusive part and a jump part). The proofs rely on an alternative approach to general Girsanov transformations in the spirit of Kunita. The case of ϕ-relative entropies is also investigated, in particular to make a link with a previous work of Billera and Diaconis on the traditional Metropolis algorithm in the discrete time setting.

Introduction

The Metropolis algorithm is a very popular Monte Carlo procedure to sample approximatively according to a given law π (cf. for instance Metropolis, Rosenbluth, Rosenbluth, Teller and Teller [START_REF] Metropolis | Equation of state calculations by fast computing machines[END_REF], Hammersley and Handscomb [START_REF] Hammersley | Monte Carlo methods[END_REF], Fishman [START_REF] Fishman | Springer Series in Operations Research[END_REF] or Liu [START_REF] Jun | Monte Carlo strategies in scientific computing[END_REF]). In discrete time and finite state space, it starts with a Markov kernel K and transform it into a kernel K π which is reversible with respect to π. Under mild assumptions, K π is ergodic so that π can be approached by simulating a Markov chain whose transitions are didacted by K π . Billera and Diaconis [START_REF] Billera | A geometric interpretation of the Metropolis-Hastings algorithm[END_REF] took a geometrical point of view on the construction of K π by introducing a distance d on the set of Markov kernels and by showing that K π is a minimizer for the distance from K to the set of Markov kernels which are reversible with respect to π. The goal of this paper is extend this point of view to continuous time, in particular via new entropy-type discrepancies among generators.

We begin by recalling more precisely the main result of Billera and Diaconis [START_REF] Billera | A geometric interpretation of the Metropolis-Hastings algorithm[END_REF]. Let S be a finite set and denote by K the set of S × S Markov matrices. We assume that we are given π a positive probability measure on S and K ∈ K. The associated Metropolis kernel K π is defined by ∀ x, y ∈ S, K π (x, y) min K(x, y), π(y) π(x) K(y, x)

, if x = y 1 -z∈S\{x} K π (x, z) , if x = y
Consider the distance d on K defined by

∀ K, K ∈ K, d(K , K) x∈S π(x) y∈S\{x} K (x, y) -K(x, y)
and K(π) the subset of K consisting of Markov matrices M which are reversible with respect to π, namely satisfying ∀ x, y ∈ S, π(x)M (x, y) = π(y)M (y, x)

Let us also denote K(π, K) the subset of K(π) consisting of Markov matrices M whose off-diagonal entries are less or equal than those of K. Billera and Diaconis [START_REF] Billera | A geometric interpretation of the Metropolis-Hastings algorithm[END_REF] proved the following result:

Theorem 1 With respect to d, the Metropolis kernel K π minimizes the distance from K to K(π) and it is the unique minimizer of the distance from K to K(π, K).

The arguments of Billera and Diaconis [START_REF] Billera | A geometric interpretation of the Metropolis-Hastings algorithm[END_REF] enable to extend immediately this result to the corresponding continuous time setting. Let L be the set of (Markov) generators on S, i.e the S × S matrices whose off-diagonal entries are nonnegative and such that the sums along the lines are zero. Let π be fixed as above and L ∈ L be given. Define the distance d on L by the same formula as before and similarly consider L(π) (respectively L(π, L)) the subset of L consisting of generators which are reversible with respect to π (resp. and whose off-diagonal entries are dominated by those of L). Finally the associated Metropolis generator L π is defined by ∀ x, y ∈ S, L π (x, y) min L(x, y), π(y) π(x) L(y, x) , if x = y

-z∈S\{x} L π (x, z) , if x = y (1)
Then we have Proposition 2 With respect to d, the Metropolis generator L π minimizes the distance from L to L(π) and it is the unique minimizer of the distance from L to L(π, L).

But this result is not satisfying, because it does not admit an obvious extension to more general generators, for instance to diffusion generators, whereas there is often an analogue to the Metropolis construction in such a setting. For example in the Euclidean space R d , let π be a probability measure with a smooth and positive density (still denoted π) with respect to the Lebesgue measure and consider the generator L /2 of the Brownian motion. Then it is well-known that the corresponding Metropolis generator should be the Langevin operator L π • ( •+ ∇ ln(π), ∇• )/2. One of our objectives is to propose a geometric justification of the latter kind of assertion, in the same spirit as Proposition 2, by providing abstract definitions of Metropolis type algorithms associated to a given probability measure and to a given Markov process. This will lead us to replace the distance d by other discrepancy quantities. To keep the development of this subject to a reasonable size and to avoid technicalities, we postpone the treatment of general Markov processes to a future work. Here we will only consider finite state space jump processes and regular diffusions taking values in a compact manifold, but we will adopt a general formalism each time it is possible without too much disgression. Nevertheless, for the remaining part of this introduction, we will keep working in the finite state space setting and the analogous results concerning compact Riemannian diffusions will be presented in section 5.

As above Proposition 2, L stands for an a priori given generator and we denote by M another generic generator. For any probability measure µ on S, we consider (X (µ) (t)) t≥0 (respectively (Y (µ) (t)) t≥0 ) a Markov process on S whose initial distribution is µ and whose generator is L (resp. M ). Without real loss of generality, their trajectories are assumed to be càdlàg, namely admitting left limits and being right continuous and for any T ∈ R + , we denote by L(X (µ) ([0, T ])) the law of X (µ) ([0, T ]) (X (µ) (t)) t∈[0,T ] on the set of càdlàg trajectories from [0, T ] to S. Recall that the relative entropy of two probability measures µ and ν given on the same probability space is defined by Ent(µ|ν)

dµ dν ln dµ dν dν ≤ +∞ , if µ ν +∞ otherwise
where dµ/dν stands for the Radon-Nikodym derivative of µ with respect to ν. This notion is convenient to introduce naturally a new discrepancy (by this term we mean a quantity satisfying the axioms of a distance, except that it is not symmetrical and that it can take the value +∞) on L. As above, π is a given positive probability measure on S, π is said to be invariant for the generator M if we have To get a better justification of the introduction of the discrepancy d, we are lacking a "computational complexity" interpretation of the relative entropy of two probability measures µ and ν, something saying heuristically that "Ent(µ|ν) is a measurement of the difficulty (or maybe of the necessary quantity of additional randomness) to simulate according to µ when we know how to simulate from ν". Sanov's theorem (see for instance the book of Dembo and Zeitouni [START_REF] Dembo | Large deviations techniques and applications[END_REF]) goes in this direction, we would like a more simulation oriented result. The above proposition may still seems disturbing, since we are using chains starting from the distribution π we want to approximate! But the discrepancy d should be seen as an asymptotic object: we will show that if π is furthermore assumed to be attractive for M , then we have for any initial distribution µ,

∀ y ∈ S,
lim T →+∞ Ent(L(Y (µ) ([0, T ]))|L(X (µ) ([0, T ])))/T = d(M, L) (2)
We can use the discrepancy d to define another Metropolis type generator:

Theorem 4 The mapping L(π) M → d(M, L) admits a unique minimizer L π which is given by

∀ x, y ∈ S, L π (x, y) π(y) π(x) L(x, y)L(y, x) , if x = y -z∈S\{x} L π (x, z) , if x = y
In particular, we don't find the usual Metropolis generator L π as in Proposition 2. To make a link between them, we need to consider more general projection procedures.

Let ϕ : R + → R + be a convex function satisfying ϕ(1) = 0, ϕ (1) = 0 (so ϕ is assumed to admits a derivative at 1) and whose growth is at most of polynomial order. We define the corresponding ϕ-relative entropy of two probability measures µ and ν given on the same probability space, by Ent ϕ (µ|ν)

ϕ dµ dν dν , if µ ν +∞ otherwise
(the previous relative entropy corresponds to the function ϕ : R + r → r ln(r) -r + 1). Contrary to the usual relative entropy case, when π is invariant with respect to M , the quantity Ent

ϕ (L(Y (π) ([0, T ]))|L(X (π) ([0, T ]))
) is no longer linear with respect to the time T ∈ R + , but we can define a discrepancy d ϕ in the following way:

Proposition 5 Without any assumption on M , we have lim

T →0 + Ent ϕ (L(Y (π) ([0, T ]))|L(X (π) ([0, T ])))/T = d ϕ (M, L)
where the discrepancy d ϕ is given by

∀ M, M ∈ L, d ϕ (M , M ) x∈S π(x) y∈S\{x} M (x, y)ϕ M (x,y) M (x,y) , if M M +∞ otherwise where M M means that ∀ x, y ∈ S, M (x, y) = 0 =⇒ M (x, y) = 0
If furthermore we assume that ϕ is strictly convex then the mapping L(π) M → d ϕ (M, L) admits a unique minimizer L ϕ,π .

To recover the usual Metropolis generator L π defined in (1), we consider for ∈ (0, 1/2], the convex function ϕ satisfying ϕ (x) = (x -1) 2 for any x ∈ [1 -, 1 + ], ϕ = -1 on [0, 1 -) and ϕ = 1 + on (1 + , +∞) (this is a kind of Huber loss function). Despite the fact that ϕ is not strictly convex, the mapping L(π) M → d ϕ (M, L) admits nevertheless a unique minimizer L ϕ ,π and we have lim

→0 + L ϕ ,π = L π (3)
The advantage of this approach is that it can be extended to more general situations than the finite state space case. For instance in the Euclidean diffusion setting, we will see that the discrepancies d ϕ do not depend on ∈ (0, 1/2] and are also equal to 2 d (this quantity will be symmetrical in this situation, but not a distance, because it can still take the value +∞). This provides a natural definition for d in this framework and "projecting" accordingly, we will recover the notion of Metropolis algorithm mentioned previously in the Brownian motion case.

The paper has the following plan. In next section we will present the analogue of Girsanov formula in the finite state space setting, which enables to compute Radon-Nikodym densities on trajectory spaces. The above assertions about relative entropy and their generalizations to ϕrelative entropies will be developped respectively in sections 3 and 4. Finally in section 5 we will extend these considerations to the compact Riemannian diffusion situation.

Finite state space Girsanov formula

This long section presents in the finite state space setting the changes of law which are analogeous to those considered by Girsanov [START_REF] Girsanov | On transforming a class of stochastic processes by absolutely continuous substitution of measures[END_REF] for Euclidean diffusions. They corresponds to all the transformations of the underlying probability measure P of a given Markov process which remain absolutely continuous with respect to P on finite time intervals and which preserve the (time-homogeneous) Markov property.

We begin by recalling the martingale problem approach to Markov processes, since it is the natural framework to deal with this subject. We need some notations: let D be the set of càdlàg trajectories from R + to the finite set S. We denote by (X(t)) t≥0 the process of the canonical coordinates on D and we endow D with the σ-field D generated by the X(t), for t ∈ R + . For any T ∈ R + , we also denote D([0, T ]) the σ-field generated by the X(t), for t ∈ [0, T ]. We will always implicitely assume that set D is endowed with the filtration (D([0, t])) t≥0 . Let a probability measure µ on S and L ∈ L be given. We say that a probability measure P on D is a solution to the martingale problem associated to µ and L if:

• The law of X(0) (called the initial law) under P is µ.

• For any function f defined on S, the process M (f ) defined by

∀ t ∈ R + , M (f ) t f (X(t)) -f (X(0)) - t 0 L[f ](X(s)) ds (4)
is a martingale. In the above expression, L was interpreted as an operator acting on functions (seen as column vector, indexed by S) through the formula

∀ x ∈ S, L[f ](x) y∈S L(x, y)f (y)
It is well-known, see for instance the book [START_REF] Stewart | Markov processes[END_REF] of Ethier and Kurtz, that such a solution exists and is unique, we denote it P µ (or simply P x when µ is equal to the Dirac mass δ x for some x ∈ S). The probabilistic description of the evolution of (X(t)) t≥0 is the following: for s > 0, let X(s-) lim u→s,u<s X(u) and consider the first jump time τ 1 inf{s > 0 : X(s) = X(s-)}. Then conditionally to X(0), τ 1 is distributed as an exponential law of parameter |L(X(0), X(0))| (this is the Dirac measure at +∞ if L(X(0), X(0)) = 0). Conditionally to X(0) and τ 1 < +∞, the first jump position X(τ 1 ) is distributed according to the law (L(X(0), y)/|L(X(0), X(0))|) y =X(0) on S \ {X(0)}. Next conditionally to X(0), τ 1 and X(τ 1 ), the waiting time for the second jump is distributed as an exponential law of parameter |L(X(τ 1 ), X(τ 1 ))| etc. If one doesn't want to make reference to a particular initial distribution µ (and this is usually the point of view adopted in Markov process theory, compare for instance Lemmas 6 and 7 below to see how convenient it can be), one considers simultaneously all the martingale problems associated to δ x and L, for x ∈ S, and one says that the solution to the martingale problems relative to L is the family (P x ) x∈S . Note that all the P µ can be recovered from this family, since we have P µ = x∈S µ(x)P x . Furthermore, he Markov property of (X(t)) t≥0 under P µ is deduced without difficulty from the uniqueness of the family (P x ) x∈S as solution to the above martingale problems.

Let L ∈ L be another generator and P µ be the solution of the martingale problem associated to µ and L. More generally all notions relative to L will be covered by a tilde sign when they have to be distinguished from those relative to L. For T ≥ 0, consider P µ,[0,T ] the restriction of P µ to the measurable space (D, D([0, T ]). We are interested in the generators L which are such that for any x ∈ S and any T ≥ 0, P x,[0,T ] is absolutely continuous with respect to P x,[0,T ] (using the Markov property, it is clear that is equivalent to the existence of T > 0 such that for any x ∈ S, P x,[0,T ] is absolutely continuous with respect to P x,[0,T ] ). A necessary condition is easy to obtain. For x ∈ S, let S x be the set of points which are attainable by X under P x : a point y ∈ S belongs to S x if and only if there exists a finite sequence x 0 = x, x 1 , ..., x n = y in S with n ∈ N and L(x i , x i+1 ) > 0 for all i ∈ 0, n -1 . More generally, let S µ ∪ x∈supp(µ) S x , where supp(µ) is the support of µ.

Lemma 6 If there exists T > 0 such that P µ,[0,T ] is absolutely continuous with respect to P µ,[0,T ] , then S µ ⊂ S µ and we have

∀ x ∈ S µ , ∀ y ∈ S, L(x, y) = 0 =⇒ L(x, y) = 0
Proof For x, y ∈ S and T > 0, consider the event

A x,y,T {∃ s ∈ (0, T ] : X(s-) = x, X(s) = y}
From the probabilistic description of P µ , we see that P µ [A x,y,T ] > 0 if and only if x ∈ S µ and L(x, y) > 0 and let denote by R µ the set of such couples (x, y). Now let T > 0 be as in the above lemma. From the absolute continuity assumption, we get that R µ ⊂ R µ and this amounts to the conclusions given in the lemma.

The necessary condition given in Lemma 6 is in fact sufficient, see remark 13 below. But to avoid embarrassing notations, it is better to work simultaneously with the whole family (P x ) x∈S . As an immediate consequence of the above result, we get:

Lemma 7 If there exists T > 0 such that for any x ∈ S, P x,[0,T ] is absolutely continuous with respect to P x,[0,T ] , then we have L L (with the notation of Proposition 5), which just means that the transitions forbidden by L are also forbidden by L.

Our main goal in this section is to show the reciprocal result and to exhibit the density d P x,[0,T ] /dP x,[0,T ] . To do so, again we need more notations.

For x = y ∈ S and t ≥ 0, consider

N (x,y) t s∈(0,t] 1 X(s-)=x,X(s)=y
the number of jumps from x to y which have occurred before time t and

M (x,y) t N (x,y) t - t 0 L(x, y)1 x (X(s)) ds
Let us check that (M (x,y) t

) t≥0 is a martingale under P µ for any initial condition µ. This comes from the fact that we can represent it as a stochastic integral:

∀ t ≥ 0, M (x,y) t = t 0 1 x (X(s-)) dM (y) s (5)
where (M (y) t ) t≥0 is the martingale associated to the indicator function 1 y via formula [START_REF] Kunita | Absolute continuity of Markov processes and generators[END_REF]. Indeed, let us compute the r.h.s.:

t 0 1 x (X(s-)) dM (y) s = t 0 1 x (X(s-)) d 1 y (X(s)) -1 y (X(0)) - s 0 L[1 y ](X(u)) du = t 0 1 x (X(s-)) d1 y (X(s)) - t 0 1 x (X(s-))L[1 y ](X(s)) ds = 0<s≤t 1 x (X(s-))(1 y (X(s)) -1 y (X(s-))) - t 0 1 x (X(s-))L[1 y ](x) ds = N (x,y) t - t 0 L(x, y)1 x (X(s)) ds
Now consider another generator L satisfying the conclusion of Lemma 7. We define

∀ x = y, A(x, y) L(x, y) L(x, y)
(taking into account the usual convention that 0 • ∞ = 0, we have A(x, y) = 0 if L(x, y) = 0, since L L). Consider also the functions G and H defined by

∀ x ∈ S, G(x) y =x L(x, y)(ln(A(x, y)) -A(x, y) + 1) H(x) -y =x L(x, y)(A(x, y) -1) = L(x, x) -L(x, x)
Then we have > 0 for some x = y satisfying L(x, y) = 0 and L(x, y) > 0). This result could be proven using Doléans-Dade stochastic exponential (cf. for instance the book of Dellacherie and Meyer [START_REF] Dellacherie | Probabilités et potentiel. Chapitres V à VIII[END_REF]) and stochastic calculus for martingales with jumps. Nevertheless this approach does not seem to us the most appropriate to deal with the present situation. Indeed, we just want to use immediate consequences of the martingale problem formulation and elementary stochastic calculus, enabling to compute the product of a absolutely continuous adapted process with a martingale. The proof of Theorem 8 will take several steps. The first one consist in introducing some exponential martingales (which are not easily described as Doléans-Dade stochastic exponential processes).

To any function f on S, we associate a new function I[f ] via the formula

∀ x ∈ S, I[f ](x) exp(-f (x))L[exp(f )](x) -L[f ](x)
Remark 9 The mapping f → I[f ] should be seen as a modified "carré du champ". Recall that the usual carré du champ of f (see for instance the lecture of Bakry [START_REF] Bakry | L'hypercontractivité et son utilisation en théorie des semigroupes[END_REF]) is defined by

∀ x ∈ S, Γ[f ](x) L[f 2 ](x) -2f (x)L[f ](x)
It is easily checked for instance that we have

exp(-osc(f ))Γ[f ] ≤ 2I[f ] ≤ exp(osc(f ))Γ[f ]
where osc(f ) = max S f -min S f is the oscillation of f . Furthermore, if L is a diffusion generator (namely if the processes admitting L as generator have continuous paths, as it will be the case in section 5), we have

I[f ] = Γ[f ]/2.
The interest of the carré du champ is that it enables to compute the bracket of M (f ) (i.e. the previsible process ( M (f ) t ) t≥0 starting from 0 such that ((M (f ) ) 2 -M (f ) t ) t≥0 is a martingale):

∀ t ≥ 0, M (f ) t = t 0 Γ[f ](X(s)) ds
The modified carré du champ will play a similar role of integrand for a compensator, but with an exponential mapping rather than a square mapping.

We associate to any function f on S the process (E t [f ]) t≥0 given by

∀ t ≥ 0, E t [f ] exp M (f ) t - t 0 I[f ](X(s)) ds (6)
Then we have another characterization of the solution to the martingale problem associated to µ and L:

Proposition 10 Under P µ the process (E t [f ]) t≥0 is a martingale. Conversely if P is a probability measure on D such that µ is the law of X(0) and such that for any function f , the process (E t [f ]) t≥0 is a martingale, then P = P µ .

Proof

For the first point, we write that for any t ≥ 0,

E t [f ] = exp - t 0 exp(-f (X(s)))L[exp(f )](X(s)) ds exp(f (X(t)) -f (X(0)))
so its stochastic differential is

dE t [f ] = exp - t 0 exp(-f (X(s)))L[exp(f )](X(s)) ds exp(-f (X(0))) (L[exp(f )](X(t))dt + dM (exp(f )) t ) + exp - t 0 exp(-f (X(s)))L[exp(f )](X(s)) ds exp(f (X(t)) -f (X(0))) exp(-f (X(t)))L[exp(f )](X(t))dt = exp - t 0 exp(-f (X(s)))L[exp(f )](X(s)) ds exp(-f (X(0)))dM (exp(f )) t It follows that (E t [f ]
) t≥0 is a martingale as a stochastic integral (of a previsible integrand) with respect to the martingale (M (exp(f )) t

) t≥0 . Conversely, we write that for any t ≥ 0, exp(f (X(t))) = exp(f (X(0))) exp

t 0 exp(-f (X(s)))L[exp(f )](X(s)) ds E t [f ] thus differentiating we get d exp(f (X(t))) = exp(f (X(0))) exp t 0 exp(-f (X(s)))L[exp(f )](X(s)) ds E t [f ] exp(-f (X(t)))L[exp(f )](X(t))dt + exp(f (X(0))) exp t 0 exp(-f (X(s)))L[exp(f )](X(s)) ds dE t [f ] = L[exp(f )](X(t))dt + exp(f (X(0))) exp t 0 exp(-f (X(s)))L[exp(f )](X(s)) ds dE t [f ] It follows that dM (exp(f )) t = exp(f (X(0))) exp t 0 exp(-f (X(s)))L[exp(f )](X(s)) ds dE t [f ]
and thus (M

(exp(f )) t ) t≥0 is a martingale if (E t [f ]) t≥0 is a martingale.
The second announced result is a consequence from the fact that any function f on S can be written as f = exp(g) -c exp(0), with c 1 -max(0, min S f ) and the function g ln(c + f ), so that

M (f ) = M (exp(g)) -cM (exp(0)) = M (exp(g)) is a martingale.
We need more exponential martingales than those of the form (E t [f ]) t≥0 where f ∈ F(S), the space of functions defined on S. Let us note that for any f ∈ F(S), we can write

∀ t ≥ 0, M (f ) t = x∈S f (x)M (x) t
This suggests to consider the new martingales

∀ t ≥ 0, M (f ) t = (x,y)∈S (2) f (x, y)M (x,y) t
where S (2) ) S 2 \ {(x, x) : x ∈ S} and f is a function defined on S (2) . We denote F(S (2) ) the space of such functions and we will also see it as a subset of F(S 2 ) by extending functions f ∈ F(S (2) ) on S 2 with the convention that they vanish on the diagonal {(x, x) : x ∈ S}. This enables to extend the modified carré du champ I as a non-linear operator from F(S (2) ) to F(S) by action on the second variable. More explicitely, we define

∀ f ∈ F(S (2) ), ∀ x ∈ S, I[f ](x) I[f (x, •)](x) = y∈S\{x} L(x, y)(exp(f (x, y)) -1 -f (x, y))
Next we associate to any f ∈ F(S (2) ) the process (E t [f ]) t≥0 via [START_REF] Stewart | Markov processes[END_REF].

Proposition 11 For any initial condition µ, the process (E t [f ]) t≥0 is a martingale under P µ .

Proof

We remark that (E t [f ]) t≥0 is a multiplicative process, in the sense that

∀ t, s ≥ 0, E t+s [f ] = E t [f ]E s [f ] • θ t
where (θ t ) t≥0 is the family of the natural shift mappings from D to itself:

∀ t, s ≥ 0, ∀ ω ∈ D, X s (θ t (ω)) = X t+s (ω)
Thus taking into account the fact that (E t [f ]) t≥0 is adapted and the Markov property, we see that to prove that (E t [f ]) t≥0 is a martingale under P µ , it is sufficient to show that

∀ t ≥ 0, ∀ x ∈ S, E x [E t [f ]] = 1
To do so, we will use Proposition 10 and an approximation procedure. Let > 0 be given. We consider the F(S)-valued previsible process (F (t)) t≥0 given by

∀ t ≥ 0, ∀ x ∈ S, F (t)(x) f (X( t/ ), x)
where • stands for a modified integer part: for any r ∈ R + , r is the largest integer number strictly less than r, with the exception that 0 = 0 (this is to insure that (F (t)) t≥0 is previsible, in fact this is also true if • is the usual integer part, but to be convinced of this assertion, one needs to know that the jump times of the underlying Markov processes are totally imprevisible and we don't want to enter in such technicalities, cf. for instance the book of Dellacherie and Meyer [START_REF] Dellacherie | Probabilités et potentiel. Chapitres V à VIII[END_REF]). Next we define

∀ t ≥ 0, M (F ) t x∈S t 0 F (s)(x) dM (x) s (7)
and quite naturally

∀ t ≥ 0, E t ( , f ) exp M (F ) t - t 0 I[F (s)](X(s)) ds
Since for t ∈ [0, ], F (t)(x) does not depend on t and depends on the underlying trajectory (X(s)) s≥0 only through X(0), the first part of Proposition 10 shows that for any initial point x ∈ S,

∀ t ∈ [0, ], E x [E t ( , f )] = 1
More generally, conditioning successively with respect to D([0, i ]), D([0, (i -1) ]), ..., D([0, ]), with i t/ , the same argument shows that

∀ t ≥ 0, ∀ x ∈ S, E x [E t ( , f )] = 1
Thus to deduce the announced result, it is sufficient to prove that for any fixed x ∈ S, t ≥ 0 and f ∈ F(S (2) ), E t ( , f ) converges to E t [f ] in L 1 (P x ) as goes to 0 + . One way to deduce this convergence is to show on one hand that sup

∈(0,1/2] E x [E 2 t ( , f )]
< +∞ and on the other hand that pointwise (P x -a.s. or even only in probability would be enough), E t ( , f ) converges to E t [f ] as goes to 0 + . For the first point, we compute that

E x [E 2 t ( , f )] = E x exp M (2F ) t -2 t 0 I[F ](X(s)) ds = E x E t ( , 2f ) exp t 0 (I[2F ] -2I[F ])(X(s)) ds ≤ exp t sup y,z∈S I[2f (y, •)](z) -2I[f (y, •)](z)
which is a finite upper bound independent from ∈ (0, 1/2].

Concerning the pointwise convergence, we note that for any s ≥ 0 and x ∈ S,

lim →0 + F (s)(x) = f (X(s-), x)
Thus, passing in the limit in [START_REF] Fishman | Springer Series in Operations Research[END_REF] (taking into account that in the finite setting the stochastic differentials dM

(x)
s can be seen as simple Stieljes differentials), we get that lim

→0 + M (F ) t = x∈S t 0 f (X(s-), x) dM (x) s = x∈S t 0 y =x f (y, x)1 {y} (X(s-)) dM (x) s = (y,x)∈S (2) f (y, x) t 0 1 {y} (X(s-))dM (x) s = (x,y)∈S (2) f (x, y)M (x,y) t = M (f ) t
where the last but one equality comes from [START_REF] Émery | Stochastic calculus in manifolds[END_REF].

We also deduce that lim

→0 + t 0 I[F (s)](X(s)) ds = t 0 I[f (X(s-), •)](X(s)) ds = t 0 I[f (X(s), •)](X(s)) ds = t 0 I[f ](X(s)) ds
(where in the second equality we have used that X(s-) = X(s) almost everywhere with respect to the Lebesgue measure ds), result leading to the wanted pointwise convergence.

Let the probability µ on S and the function f ∈ F(S (2) ) be fixed. For any t ≥ 0, consider P µ,[0,t] the probability on the measurable space (D, D([0, t])) which admits E t [f ] as density with respect to P µ,[0,t] . Since the process (E s [f ]) s≥0 is a nonnegative martingale starting from 1, it is easy to deduce that the family ( P µ,[0,t] ) t≥0 satisfies the compatibility relations of Kolmogorov: for 0 ≤ s ≤ t, the restriction of

P µ,[0,t] to (D, D([0, s])) is equal to P µ,[0,s]
. By consequence there exists a unique probability measure P µ on (D, D) such that for any t ≥ 0, the restriction of

P µ to (D, D([0, t])) coincides with P µ,[0,t] .
Next result is the key to Theorem 8.

Theorem 12

The probability P µ is solution to the martingale problem associated to µ and to the generator L defined by

∀ x, y ∈ S, L(x, y) L(x, y) exp(f (x, y)) , if x = y -z∈S\{x} L(x, z) , if x = y

Proof

We use the criterion presented in Proposition 10. The law of X(0) under P µ is µ since P µ and P µ coincides on the σ-field D([0, 0]) = σ(X(0)). So let g ∈ F(S) be a test function. We want to show that ( E t [g]) t≥0 is a martingale under P µ , where

∀ t ≥ 0, E t [g] exp M (g) t - t 0 I[g](X(s)) ds with of course, ∀ t ≥ 0, M (g) t g(X(t)) -g(X(0)) - t 0 L[g](X(s)) ds = M (g) t - t 0 ( L -L)[g](X(s)) ds ∀ x ∈ S, I[f ](x) exp(-f (x)) L[exp(f )](x) -L[f ](x)
Due to the definition of P µ , (

E t [g]) t≥0 is a martingale under P µ if and only if ( E t [g]E t [f ]
) t≥0 is a martingale under P µ . But for any t ≥ 0, we compute that

E t [g]E t [f ] = exp M (g) t + M (f ) t - t 0 F (X(s)) ds
where F ∈ F(S) is the function defined by, for any x ∈ S,

F (x) ( L -L)[g](x) + exp(-g(x)) L[exp(g)](x) -L[g](x) + L[exp(f (x, •)](x) -L[f (x, •)](x) = exp(-g(x)) L[exp(g)](x) + L[exp(f (x, •)](x) -L[g + f (x, •)](x) = y =x (exp(g(y) -g(x)) -1) L(x, y) + (exp(f (x, y)) -1)L(x, y) -L[g + f (x, •)](x) = y =x [exp(g(y) -g(x)) -1] exp(f (x, y)) + exp(f (x, y)) -1 L(x, y) -L[g + f (x, •)](x) = y =x (exp[g(y) -g(x) + f (x, y)] -1) L(x, y) -L[g + f (x, •)](x) = I[h](x)
with h ∈ F(S (2) ) given by ∀ (x, y) ∈ S (2) , h(x, y) g(y) -g(x) + f (x, y)

Let us check that

∀ t ≥ 0, M (g) t + M (f ) t = M (h) t
It amounts to verify that M (g) = M (ḡ) where ḡ ∈ F(S (2) ) is defined by

∀ (x, y) ∈ S (2) , ḡ(x, y) g(y) -g(x)
Indeed, we have for any t ≥ 0,

M (ḡ) t = (x,y)∈S (2) (g(y) -g(x))M (x,y) t = (x,y)∈S (2) (g(y) -g(x)) t 0 1 {x} (X(s-)) dM (y) s = (x,y)∈S 2 (g(y) -g(x)) t 0 1 {x} (X(s-)) dM (y) s = y∈S g(y) t 0 x∈S 1 {x} (X(s-)) dM (y) s - x∈S g(x) t 0 1 {x} (X(s-)) d   y∈S M (y) s   = y∈S g(y) t 0 dM (y) s - x∈S g(x) t 0 1 {x} (X(s-)) dM (1) s ) = y∈S g(y)M (y) t = M (g) t
where for the last but one equality we have used that the martingale associated to the function identically equal to one, M (1) , is null. So finally we get that (

E t [g]E t [f ]) t≥0 =(E t [h]
) t≥0 is a martingale under P µ according to Proposition 11.

We can now come to the

Proof of Theorem 8

So let be given a generator L satisfying L L. Be begin by assuming that L satisfies furthermore L L. Then we consider the previous construction with the function f ∈ F(S (2) ) defined by

∀ (x, y) ∈ S (2) , f (x, y) ln L(x, y) L(x, y)
According to Theorem 12, we have

∀ T ≥ 0, d P µ,[0,T ] dP µ,[0,T ] = E T [f ]
and this can be rewritten under the form given in Theorem 8.

In the general case, we introduce for > 0 the new generator L ( ) L + L, to which we apply the above result. Then with obvious notations, we get that for any T > 0, lim

→0 + exp   x =y∈S ln(A ( ) (x, y))N (x,y) T + T 0 H ( ) (X(s)) ds   = exp   x =y∈S ln(A(x, y))N (x,y) T + T 0 H(X(s)) ds  
Furthermore this pointwise convergence also takes place in L p (P µ,[0,T ] ), for any p ≥ 1, because it is not difficult to find three constants K 1 , K 2 , K 3 ≥ 0 (depending only on T , L and L) such that for any ∈ (0, 1], the random variable

x =y∈S ln(A ( ) (x, y))N (x,y) T + T 0 H ( ) (X(s)) ds is stochastically bounded above by K 1 N + K 2 ,
where N is a Poisson variable of parameter K 3 , and the latter random variable admits exponential moments of all order. We deduce that as → 0 + , the probability P ( ) µ,[0,T ] converges in total variation toward the probability P µ,[0,T ] on (D, D([0, T ])) which has exp

x =y∈S ln(A(x, y))N (x,y) T + T 0 H(X(s)) ds as density with respect to P µ,[0,T ] . It follows that the family ( P µ,[0,T ] ) T ≥0 satisfies the Kolmogorov compatibility conditions, so that its elements are the restrictions to the σ-fields (D([0, T ])) T ≥0 of a probability P µ on (D, D). Furthermore the above convergence in total variation and the convergence of L ( ) to L imply that P µ is the solution of the martingale problem associated to µ and L, i.e. P µ = P µ . Thus the conclusions of Theorem 8 also hold in the general case.

We end up this section with two remarks.

Remark 13 Let us justify the already announced fact that the necessary condition given in Lemma 6 is also sufficient. So let L a generator satisfying the conclusions of this lemma. Let L be another generator such that

∀ x ∈ S µ , ∀ y ∈ S, L(x, y) = L(x, y)
Then P µ is also solution to the martingale problem associated to µ and L, because for any f ∈ F(S) and any t ≥ 0 we have

t 0 L[f ](X(s)) ds = t 0 L[f ](X(s)) ds, P µ -a.s. In particular consider L defined by ∀ x, y ∈ S, L(x, y) L(x, y) , if x ∈ S µ 0 , otherwise
Since L L, we can apply Theorem 8 to get that for any T ≥ 0, P µ,[0,T ] P µ,[0,T ] (and the expressions for the density given in Theorem 8 are also valid, with L and L).

The second remark goes in the direction of an abstract Girsanov theory.

Remark 14

The carré du champ alluded to in Remark 9 can be polarized into a bilinear map from F(S) 2 to F(S) via the formula

∀ f, g ∈ F(S), ∀ x ∈ S, Γ[f, g](x) L[f g](x) -f (x)L[g](x) -g(x)L[f ](x)
Next, similarly to what we have done before Proposition 11, we can extend Γ to F(S 2 ) by action on the second variable:

∀ f, g ∈ F(S 2 ), ∀ x ∈ S, Γ[f, g](x) Γ[f (x, •), g(x, •)](x)
Now let a function f ∈ F(S (2) ) be fixed and consider the generator L constructed in Theorem 12.

Then its action on functions can be expressed under the form

∀ g ∈ F(S), ∀ x ∈ S, L[g](x) = L[g](x) + Γ[exp(f ), g](x)
(where g in the carré du champ is considered as a function of the second variable). This procedure associating to a bivariate function f ∈ F(S (2) ) an exponential martingale (E t [f ]) t≥0 which leads to the construction of the solution to the martingale problem corresponding to the operator L given in the above form is in fact very general (this is investigated in a general martingale problem framework in [START_REF] Miclo | An introduction to Markov processes[END_REF]). Indeed, under regularity assumptions, we can recover in this way all the transformations of the underlying probability of a Markov process which preserve the Markov property and which are absolutely continuous over finite time horizons. These generalized Girsanov transformations were first exihibited by Kunita [12] which used another formalism. Heuristically, these changes amounts to modifying the intensity of jumps and adding drifts in the directions permitted by the diffusion coefficients. According to the above formulation, they can be parametrized by functions belonging to subspaces of F(S (2) ) (satisfying some regularity or boundedness assumptions in general) quotiented by the subspace of bivariate functions whose carré du champ vanishes everywhere. For instance starting with the Laplacian generator over a Riemannian compact manifold, we recover all the vector fields as parameters of Girsanov transformations in this setting, see also the discussion after Proposition 24 in section 5.

Entropy minimization

This section contains all the considerations concerning relative entropy mentioned in the introduction. In particular we prove Proposition 3 and Theorem 4.

In order to deal with Proposition 3 and ( 2) by the same computation, we first consider an arbitrary initial condition µ on S. Recall that (X (µ) (t)) t≥0 (respectively (Y (µ) (t)) t≥0 ) is a Markov process on S whose initial distribution is µ and whose generator is L (resp. M ). For t ≥ 0, we denote by µ t the law of Y (µ) (t). We also introduce the extended function F (F does not necessary belong to F(S), because it can take +∞ as value) defined by

∀ x ∈ S, F (x) y∈S\{x} M (x, y) ln M (x, y) L(x, y) -M (x, y) + L(x, y)
(in particular, F (x) = +∞ is equivalent to the fact that there exist y = x such that L(x, y) = 0 and M (x, y) > 0). These notations enable to compute the relative entropy of interest:

Lemma 15 For any T ≥ 0, we have

Ent(L(Y (µ) ([0, T ]))|L(X (µ) ([0, T ]))) = T 0 µ t [F ] dt

Proof

Assume first that M L. Then according to Theorem 8, the Radon-Nikodym density of

L(Y (µ) ([0, T ])) with respect to L(X (µ) ([0, T ])) is given by dL(Y (µ) ([0, T ])) dL(X (µ) ([0, T ])) (X([0, T ])) = exp   (x,y)∈S (2) ln(A(x, y))N (x,y) T + T 0 H(X(s)) ds   (recall that (X(t)) t≥0 is a generical trajectory of D), with ∀ x ∈ S, H(x) M (x, x) -L(x, x) ∀ (x, y) ∈ S (2) , A(x, y) M (x, y) L(x, y) Thus the entropy Ent(L(Y (µ) ([0, T ]))|L(X (µ) ([0, T ]))
) is equal to the expectation with respect to L(Y (µ) ([0, T ])) of (x,y)∈S (2) ln(A(x, y))N (x,y) T + T 0 H(X(s)) ds (with the convention that this expectation is +∞ if the latter expression is not integrable). Taking into account that for any (x, y) ∈ S (2) , (N

(x,y) t - t 0 M (x, y)1 x (X(s)) ds) t∈[0,T ] is a martingale under L(Y (µ) ([0, T ])), which is (L(Y (µ) ([0, T ]))-a.s. identically null if A(x, y) = 0, we can write Ent(L(Y (µ) ([0, T ]))|L(X (µ) ([0, T ]))) = E   (x,y)∈S (2) T 0 ln(A(x, y))1 x (Y (µ) (t)) dt + T 0 H(Y (µ) (t)) dt   = E T 0 F (Y (µ) (t)) dt = T 0 E F (Y (µ) (t)) dt = T 0 µ t [F ] dt
so we get the announced equality. We now come to the general case. Let S µ be the set of points attainable by Y (µ) (defined before Lemma 6, with L replaced by M ). According to Remark 13, the above arguments are still valid if we have

∀ x ∈ S µ , ∀ y ∈ S, L(x, y) = 0 =⇒ M (x, y) = 0
But if the latter condition is not satisfied, then on one hand for

T > 0, L(Y (µ) ([0, T ])) is not absolutely continuous with respect to L(X (µ) ([0, T ])) and thus L(Y (µ) ([0, T ]))|L(X (µ) ([0, T ])) = +∞.
On the other hand, there exists x ∈ S µ such that F (x) = +∞. But from the probabilistic description of Y (µ) , it appears that for any t > 0, µ t gives positive weight to any point of S µ and in particular µ t [F ] = +∞. It follows that in this situation the equality of the above lemma is also true for T > 0, since both terms are equal to +∞. For T = 0, the equality holds because both terms are clearly null.

Proposition 3 follows immediately: if µ is invariant for M we have µ t = µ for all t ≥ 0, so for any

T ≥ 0, Ent(L(Y (µ) ([0, T ]))|L(X (µ) ([0, T ]))) = T µ[F ]
and one would have noticed that π[F ] = d(M, L). Concerning (2), the assumption that π is attractive for M means that for any initial condition µ, we have

lim t→+∞ µ t = π
Thus Cesaro's lemma enables to conclude to (2), at least if F is a true function. But if F takes the value +∞ at some point of S, the hypothesis that π is positive on S implies that d(M, L) = +∞. On the other hand the attractive assumption of π with respect to M is well-known to be equivalent to the fact that M is irreducible. This implies that for any initial distribution µ, S µ = S and by consequence, for any T > 0, the law L(Y (µ) ([0, T ])) cannot be absolutely continuous with respect to L(X (µ) ([0, T ])) (see Remark 13). It follows that the l.h.s. of ( 2) is also equal to +∞.

One advantage of the discrepancy d over the distance d introduced by Billera and Diaconis [START_REF] Billera | A geometric interpretation of the Metropolis-Hastings algorithm[END_REF] is that we don't need an extra condition to define the projection on L(π) with respect to d, as it will be clear in the

Proof of Theorem 4

Put an arbitrary total ordering on S, whose strict inequality is denoted ≺. The fact that M ∈ L(π) is equivalent to the fact that

∀ x ≺ y, M (y, x) = π(x) π(y) M (x, y)
and in particular M is determined by the free choice of the quantities M (x, y) ≥ 0 for x ≺ y. This leads us to write

d(M, L) = x≺y π(x)M (x, y) ln M (x, y) L(x, y) -π(x)M (x, y) + π(x)L(x, y) +π(y)M (y, x) ln M (y, x) L(y, x) -π(y)M (y, x) + π(y)L(y, x) = x≺y π(x)M (x, y) ln π(x)M (x, y) π(x)L(x, y) -2π(x)M (x, y) + π(x)L(x, y) +π(x)M (x, y) ln π(x)M (x, y) π(y)L(y, x) + π(y)L(y, x) = x≺y π(x)M (x, y) ln (π(x)M (x, y)) 2 π(x)L(x, y)π(y)L(y, x) -2π(x)M (x, y) + π(x)L(x, y) + π(y)L(y, x)
It appears that if we want to find a minimizer M ∈ L(π) of d(M, L), we can minimize each summand of the above sum separately. So let x ≺ y be fixed and denote

∀ x = y, L π (x, y) ≤ L π (x, y)
and it follows that the Markov process associated to L π goes faster to equilibrium than that associated to L π , if we measure this property by the spectral gap or by the logarithmic Sobolev constant (see for instance the lectures given by Saloff-Coste [START_REF] Saloff-Coste | Lectures on finite Markov chains[END_REF]). Nevertheless the speed of convergence should not be the unique criterion for choosing a Metropolis algorithm (otherwise one would just multiply L π by a big constant) as the numbers of operations by unit time should also be taken into account. Furthermore, the initial generator L should also play a role, maybe in the spirit of the discussion below Proposition 3.

To finish this section, let us discuss an algebraic property of the mapping (L, π) → L π :

Remark 16 If π and π are two positive probability measures on S, we denote π • π the positive probability measure ππ /Z where Z x∈S π(x)π (x) is the renormalizing factor. Let us also denote P π the mapping L L → L π . Then we check directly that we have P π•π = P π • P π .

In particular, when L ∈ L admits an invariant probability measure µ which is positive, the construction of L π can be seen as a two steps procedure: -First we symmetrize L into L (= P µ (L)) defined by

∀ x = y ∈ S, L(x, y) L(x, y)L * (x, y)
where L * corresponds to the dual generator of L in L 2 (µ):

∀ x = y ∈ S, L * (x, y) µ(y) µ(x) L * (y, x)
-Next we "reweight" L into L π using f = dπ/dµ the Radon-Nikodym derivative of π with respect to µ:

∀ x = y ∈ S, L π (x, y) f (y) f (x) L(x, y)

Other Metropolis type projections

In order to better understand the difference between L π and L π , we generalize here the projection procedure of the previous section.

We work in the finite state space setting as above: for any probability measure µ on S, we consider (X (µ) (t)) t≥0 a Markov process on S whose initial distribution is µ and whose generator is L and we will denote by P µ the probability measure on the underlying probability space Ω (only the image of P µ by (X (µ) (t)) t≥0 will be important, so we could restrict ourselves to the canonical situation where Ω = D and P µ is the solution of the martingale problem associated to µ and L). For any (x, y) ∈ S (2) and t ≥ 0, N (x,y) t s∈(0,t] 1 {X (µ) (s-)=x, X (µ) (s)=y} is the number of jumps from x to y in the time interval (0, t] and

∀ t ≥ 0, N t (x,y)∈S (2) N (x,y) t
is the total number of jumps before time t. From the probabilistic description of (X (µ) (t)) t≥0 , it appears that the process (N t ) t≥0 is stochastically dominated by ( Nt ) t≥0 , a Poisson process of parameter l max x∈S |L(x, x)|. The following preliminary result is well-known.

Lemma 17 For any t ≥ 0 and (x, y) ∈ S (2) , consider the events

Ω t,x,x {N t = 0} Ω t,x,y {N (x,y) t = N t = 1} Ω t,x Ω \ y∈S Ω t,x,y
Then we have 2) be given, using the martingale problem for the indicator function of y, we get that lim

lim t→0 + 1 -P x [Ω t,x,x ] t = -L(x, x) lim t→0 + P x [Ω t,x,y ] t = L(x, y) lim t→0 + P x [ Ω t,x ] t 2 < +∞ Proof Let (x, y) ∈ S (
t→0 + P x [X (x) (t) = y] t = L(x, y)
But for any t ≥ 0, we have

{X (x) (t) = y} Ω t,x,y ⊂ {N t ≥ 2}
where is the symmetrical difference between sets. Taking into account the stochastic domination of (N t ) t≥0 by ( Nt ) t≥0 , it appears that P x [{X (x) (t) = y} Ω t,x,y ] is at most of order t 2 for small t > 0. The second convergence announced in the lemma follows. The first one is obtained in the same way, since we also have lim

t→0 + 1 -P x [X (x) (t) = x] t = -L(x, x)
The last assertion of the lemma is due to the fact that Ω t,x is included into {N t ≥ 2}.

For the next result, let ϕ : R + → R be a locally bounded function vanishing at 1 and whose growth is at most of polynomial order at +∞. Let also be given a family (a(x, y)) (x,y)∈S (2) of elements from R {-∞} (in fact only the quantities a(x, y) with L(x, y) > 0 will play a role).

Lemma 18

We have for any initial distribution µ,

lim t→0 + t -1 E µ   ϕ   exp   (x,y)∈S (2) a(x, y)N (x,y) t       =
(x,y)∈S (2) µ(x)L(x, y)ϕ(exp(a(x, y)))

Proof

We begin by remarking that for any b ≥ 0, we can find a constant c(b) ∈ R + such that

∀ t ≥ 0, E µ   exp   b y∈S\{x} a + (x, y)N (x,y) t     ≤ exp(tc(b))
(where for any r ∈ R {-∞}, r -max(r, 0)). Indeed, define the function H b ∈ F(S) by

∀ x ∈ S, H b (x) - y∈S\{x} L(x, y)(exp(ba + (x, y)) -1)
then according to Theorem 8, for any t ≥ 0, the functional exp   (x,y)∈S (2) a + (x, y)N (x,y) t

+ t 0 H b (X (µ) (s)) ds  
is a density under P µ , so it is sufficient to take

c(b) -min x∈S H b (x)
In particular the expectations considered in the lemma are well defined and we can write for any t > 0 and x ∈ S,

E x   ϕ   exp   (x,y)∈S (2)
a(x, y)N

(x,y) t       = E x   1 Ω t,x ,x ϕ   exp   (x,y)∈S (2)
a(x, y)N

(x,y) t       + y ∈S\{x } E x   1 Ω t,x ,y ϕ   exp   (x,y)∈S (2)
a(x, y)N

(x,y) t       +E x   1 Ω t,x ϕ   exp   (x,y)∈S (2) a(x, y)N (x,y) t      
The first term of the r.h.s. is null, since ϕ(1) = 0. The second term is equal to

y ∈S\{x } ϕ(a(x , y ))P x Ω t,x ,y ∼ t y ∈S\{x } ϕ(a(x , y ))L(x , y )
as t goes to 0 + . Concerning the third term, we bound it using Hölder inequality with conjugate exponents 1 < p, q < +∞,

E x   1 Ω t,x ϕ   exp   (x,y)∈S (2)
a(x, y)N

(x,y) t       ≤ P x [ Ω t,x ] 1 p   E x   |ϕ| q   exp   (x,y)∈S (2) a(x, y)N (x,y) t         1 q ≤ P x [ Ω t,x ] 1 p   E x   K q exp   qr (x,y)∈S (2) a(x, y)N (x,y) t       1 q ≤ K P x [ Ω t,x ] 1 p   E x   exp   qr (x,y)∈S (2) a + (x, y)N (x,y) t       1 q ≤ P x [ Ω t,x ] 1 p K exp(tc(rq)/q)
where K, r ≥ 0 are such that we have

∀ s ∈ R + , |ϕ(s)| ≤ Ks r
So if we choose p ∈ (1, 2), Lemma 17 shows that lim (2) a(x, y)N Now let us assume furthermore that ϕ is convex and differentiable at 1 with ϕ (1) = 0. Let also be given h ∈ F(S). Then the addition of the additive functional associated to h in the exponential does not change the previous result:

t→0 + t -1 E x   1 Ω t,x ϕ   exp   (x,y)∈S
Lemma 19 We have for any initial distribution µ,

lim t→0 + t -1 E µ   ϕ   exp   (x,y)∈S (2)
a(x, y)N

(x,y) t + t 0 h(X (µ) (s)) ds       = (x,y)∈S (2)
µ(x)L(x, y)ϕ(exp(a(x, y)))

Proof

To simplify the notations, let us write for any t ≥ 0, N (a) t (x,y)∈S (2) a(x, y)N (x,y) t

. In view of Lemma 18, it is sufficient to prove that lim

t→0 + t -1 E µ ϕ exp N (a) t + t 0 h(X (µ) (s)) ds -E µ ϕ exp N (a) t = 0 (8)
We denote by ϕ + the right derivative of ϕ (recall that it exists since ϕ is convex) and we begin by assuming furthermore that ϕ + (0) > -∞. Writing that for any s ∈ R + we have

ϕ + (0) ≤ ϕ + (s) ≤ ϕ(2s) -ϕ(s) s ≤ ϕ (2s) s
(ϕ is nonnegative since ϕ (1) = 0) it appears that ϕ + is locally bounded and that its growth is at most of polynomial order at +∞. Thus it exist K , r ≥ 0 such that

∀ s ∈ R + , ϕ + (s) ≤ K s r
This leads to the following bound, with the function ψ : R + s → sϕ + (s),

ϕ exp N (a) t + t 0 h(X (µ) (s)) ds -ϕ exp N (a) t = t 0 h(X (µ) (s)) ds 1 0 ψ exp N (a) t + u t 0 h(X (µ) (s)) ds du ≤ K h ∞ t exp (r + 1)[N (a + ) t + h ∞ t]
We deduce that the l.h.s. of ( 8) is bounded above by

K h ∞ exp((1 + r ) h ∞ t)E µ exp (r + 1)N (a + ) t
According to Lemma 18 applied with a + , the latter expectation is of order t for small t > 0, in particular the above expression vanishes as t goes to zero, so (8) is proven. It remains to deal with the case where ϕ + (0) = -∞. Let η = min(1/2, min (x,y)∈S (2) exp(a(x, y))) and consider ϕ, ϕ : R + → R + two convex functions which coincide with ϕ on [η, +∞), which are affine on [0, η] and which satisfy ϕ ≤ ϕ ≤ ϕ on R + . By the above proof, we have with ψ = ϕ or ψ = ϕ, (2) µ(x)L(x, y)ψ(exp(a(x, y))) = (x,y)∈S (2) µ(x)L(x, y)ϕ(exp(a(x, y)))

lim t→0 + t -1 E µ ψ exp N (a) t + t 0 h(X (µ) (s)) ds = (x,y)∈S
The announced result then follows by comparison.

We can now come to the

Proof of Proposition 5

So let π be a positive probability measure on S and besides (X (π) (t)) t≥0 , we are given (Y (π) (t)) t≥0 a Markov process on S whose initial distribution is π and whose generator is M . We first assume that M L. Then according to Theorem 8, we have for any T ≥ 0,

Ent ϕ (L(Y (π) ([0, T ]))|L(X (π) ([0, T ]))) = E π   ϕ   exp   (x,y)∈S (2)
a(x, y)N

(x,y) T + T 0 h(X (µ) (s)) ds       with ∀ x ∈ S, h(x) M (x, x) -L(x, x) ∀ (x, y) ∈ S (2) , a(x, y) ln M (x, y) L(x, y) ∈ R {-∞}
The convergence announced in Proposition 5 is then an immediate consequence of Lemma 19. If the property M L is not satisfied, we have, because π is positive and according to Lemma 7, that for any T > 0, L(Y (π) ([0, T ])) is not absolutely continuous with respect to L(X (π) ([0, T ])). So due to our conventions, the first part of Proposition 5 is also valid.

The proof of the second part is similar to that of Theorem 4, except we cannot give an explicit formula for the minimizer L ϕ,π . Again we consider an arbitrary total ordering on S, whose strict inequality is denoted ≺. where Φ is defined by

∀ α, β, β ≥ 0, Φ β,β (α) βϕ α β + β ϕ α β (9)
(the convention that zero multiplied by anything is still zero is always enforced). In the above sum, if x ≺ y are such that L(x, y) = 0 or L(y, x) = 0, then we must have

M (x, y) = 0, since M L. So to find a minimizer M ∈ L(π) of d ϕ (M, L) is equivalent to find a minimizer M ∈ L(π) with M L of the expression x y Φ π(x)L(x,y),π(y)L(y,x) (π(x)M (x, y))
where x y means that x ≺ y with L(x, y) > 0 and L(y, x) > 0. Since each summand of the above sum can be minimized separately, we are led to show that for any given (β, β ) ∈ (R * + ) 2 , the mapping R + α → Φ β,β (α) admits a unique minimizer α β,β ∈ R + (note that by symmetry we will have α β,β = α β ,β ). The unique minimizer L ϕ,π of L(π) M → d ϕ (M, L) will then be given by ∀ (x, y) ∈ S (2) , L ϕ,π (x, y)

1 π(x) α π(x)L(x,y),π(y)L(y,x) , if x y or if y x 0 , otherwise
So let us come back to the problem of minimizing φ Φ β,β , where (β, β ) ∈ (R * + ) 2 are assumed to be fixed. The function φ is convex and let us denote by φ + its right derivative. To see that Φ admits α * as unique minimizer is equivalent to show that

∀ α ∈ R + , φ + (α) < 0 , if α < α * > 0 , if α > α * (10)
We compute that

∀ α ∈ R + , φ + (α) ϕ + α β + ϕ + α β
By the fact that ϕ (1) = 0 and the strict convexity of ϕ, it appears that for α > 0 sufficiently small φ + (α) < 0, that for α > 0 sufficiently large φ + (α) > 0 and that φ + is increasing, thus there exists a unique α * > 0 such that ( 10) is satisfied.

In fact the strict convexity condition of Proposition 5 to get the uniqueness of the minimizer can be relaxed. To go in this direction, let us introduce

D + {t ∈ R + : λ((ϕ + ) -1 ({t})) > 0} D - {t ∈ R + : λ((ϕ + ) -1 ({-t})) > 0}
(where λ denotes the Lebesgue measure), which correspond to the nonnegative slopes of ϕ where ϕ is locally affine and respectively to the opposites of the nonpositive slopes of ϕ where ϕ is locally affine. The strict convexity of ϕ is equivalent to the fact that D -∪ D + = ∅. The last part of Proposition 5 can be improved as follows:

Proposition 20 Assume that D -∩ D + = ∅, then the mapping L(π) M → d ϕ (M, L) admits a unique minimizer L ϕ,π .

Proof

As in the proof of Proposition 5, we consider the mapping φ Φ β,β , where (β, β ) ∈ (R * + ) 2 are fixed and where Φ β,β is defined in [START_REF] Hammersley | Monte Carlo methods[END_REF]. To get the wanted uniqueness, it is sufficient to check that [START_REF] Han | Isometric embedding of Riemannian manifolds in Euclidean spaces[END_REF] is satisfied for some α * > 0. Assume that this is not true, then there would exist 0 < α -< α + such that φ + = 0 on (α -, α + ), which means that

∀ α ∈ (α -, α + ), ϕ + α β = -ϕ + α β
But the l.h.s. is nondecreasing as a function of α while the r.h.s. is nonincreasing, so we deduce that both ϕ +

• β and ϕ + • β
should be constant on the interval (α -, α + ). Denoting l the absolute value of these constants (one being the opposite of the other), we would get that l ∈ D -∩ D + , which is in contradiction with our assumption.

In fact the condition given in the above proposition is optimal:

Remark 21 Assume that the convex function ϕ (still satisfying ϕ(1) = ϕ (1) = 0) is such that for any L ∈ L, the mapping L(π) M → d ϕ (M, L) admits a unique minimizer, then we have D -∩ D + = ∅. Indeed, let l ∈ D -∩ D + , then we can find 0 < β < β and 0 < α -< α + such that

∀ α ∈ (α -, α + ), ϕ + α β = -ϕ + α β = l
It follows that Φ β,β admits the whole interval [α -, α + ] as minimizers. So according to the proof of Proposition 5, if L ∈ L is such that for some x = y we have π(x)L(x, y) = β and π(y)L(y, x) = β , then we can freely choose the value of π(x)M (x, y) = π(y)M (y, x) inside [α -, α + ] for a minimizer M of d ϕ (•, L) on L(π).

We can now justify the first assertion made after Proposition 5. So let ∈ (0, 1/2] be given Looking closely at these arguments, it appears that the situation with d instead of d ψ is similar, except we don't have to take into account the absolutely continuity constraint and we end up with the condition given in the proposition.

In particular, it appears that if there exists (x, y) ∈ S (2) with L(x, y) = 0 and L(y, x) > 0, then some of the minimizers M of d(•, L) on L(π) do not satisfy M L. We can now come to the Proof of the convergence (3) If (x, y) ∈ S (2) is such that L(x, y)L(y, x) = 0, then we have for any ∈ (0, 1/2], L ϕ ,π (x, y) = 0 = L π (x, y) and the convergence (3) is trivial. So consider (x, y) ∈ S (2) with 0 < β < β where β π(x)L(x, y) and β π(y)L(y, x). For ∈ (0, 1/2], let α * ( ) be defined as in [START_REF] Han | Isometric embedding of Riemannian manifolds in Euclidean spaces[END_REF] but with ϕ replaced by ϕ . According to the proofs of Propositions 5 and 22, we have L ϕ ,π (x, y) = α * ( )/π(x) and the convergence lim

→0 + L ϕ ,π (x, y) = L π (x, y) is equivalent to the fact that lim →0 + α * ( ) = β
But this convergence is a consequence of the observation that

∀ s ∈ [0, (1 -)β), (φ ) (s) = -2(1 + ) ∀ s ∈ ((1 + )β, ( 1
-)β ), (φ ) (s) = which implies that α * ( ) ∈ [(1 -)β, (1 + )β].
But the above result should not lead one to think that if (ϕ ) ∈(0, 0 ] , for some 0 > 0, is another family of functions satisfying the assumption of Proposition 20 and converging to ψ : R + u → |u -1| for small > 0, then (3) is fulfilled. Indeed, consider for ∈ (0, 1/2], the convex function ϕ defined by ϕ (x) = (1 -x) 2 for any x ∈ [1 -, 1 + ], ϕ = -1 -on [0, 1 -) and ϕ = 1 on (1 + , +∞). Then computations similar to the previous ones show that lim

→0 + L ϕ ,π = L π with ∀ (x, y) ∈ S (2) , L π (x, y) max L(x, y), π(y) π(x) L(y, x) , if L(x, y)L(y, x) > 0 0 , otherwise
Conversely, one should neither think that all the minimizers M described in Proposition 22 could be approached by minimizers of discrepancies as in Proposition 20. Indeed, this is clear for minimizers M not satisfying M L, but even some minimizers satisfying this condition cannot be approached. Consider for instance the case where there exist (x, y) ∈ S (2) and (x , y ) ∈ S (2) with {x, y} = {x , y } and π(x)L(x, y) = π(x )L(x , y ) < π(y)L(y, x) = π(y )L(y , x ). Then there are some minimizers M such that π(x)M (x, y) = π(x )M (x , y ), while for any convex function ϕ satisfying the assumption of Proposition 20, we have π(x)L ϕ,π (x, y) = π(x )L ϕ,π (x , y ).

Remark 23 The consideration of Proposition 22 can be extended to other discrepancies on L. For instance for > 0, consider the (non symmetrical) discrepancy

∀ M, L ∈ L, d (M, L) x∈S π(x) y∈S\{x} ( K (x, y) -K(x, y) + (K (x, y) -K(x, y)) + (12)
(where (•) + stands for the positive part). Then it appears that the mapping L(π) M → d (M, L) admits the usual Metropolis generator L π as unique minimizer (if one replace the positive part by the negative part in the above discrepancy, one gets the previously defined generator L π ). But Lemma 19 is not clear for the corresponding convex function R + u → |u -1| + (u -1) + and this alternative definition L π does not extend either to the diffusion situation.

On the compact Riemannian diffusion situation

We now leave the finite state space setting to see how our previous considerations can be extended to a compact Riemannian diffusion framework. As our main purpose is to illustrate how the approach of the previous sections can be generalized, we will adopt strong regularity assumptions.

That is also why we have chosen a compact setting, to avoid the investigation of boundedness conditions.

So let S be a smooth compact manifold of dimension n ∈ N * . We are interested into Markov generators L of diffusion type, which can be written in a chart C as

∀ f ∈ C ∞ , ∀ x ∈ S, L[f ](x) 1 2 i,j∈ 1,n a i,j (x)∂ i,j f (x) + i∈ 1,n b i (x)∂ i f (x) (13)
where C ∞ is the space of smooth functions on S, where ∂ i is the differentiation operator with respect to the i th coordinate of the underlying chart C, ∂ i,j = ∂ i ∂ j and where the diffusive symmetric matrix field C x → a(x) (a i,j (x)) i,j∈ 1,n and the drift vector field C x → b(x) (b i (x)) i∈ 1,n are smooth. Furthermore a(x) is assumed to be invertible for all x ∈ C.

If we are given a probability measure µ on S, it is well-known (see for instance the books of Emery [START_REF] Émery | Stochastic calculus in manifolds[END_REF] and of Ikeda and Watanabe [START_REF] Ikeda | Stochastic differential equations and diffusion processes[END_REF]) that we can associate to µ, seen as the initial distribution, and to the generator L a Markov process (X (µ) (t)) t≥0 with continuous trajectories in S (a Markov process with continuous trajectories is traditionally called a diffusion). The law P µ of (X (µ) (t)) t≥0 on the space of continuous mappings from R + to S is characterized as the unique solution of the martingale problem associated to µ and L:

• The law of X (µ) (0) is µ.

• For any function f ∈ C ∞ , the process M (f ) defined by

∀ t ∈ R + , M (f ) t f (X (µ) (t)) -f (X (µ) (0)) - t 0 L[f ](X (µ) (s)) ds (14)
is a martingale. For more informations on martingale problems associated to diffusion operators, 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].

The generator L and the Markov process (X (µ) (t)) t≥0 should be seen as an a priori given Markov framework and they will play exactly the same role they had in the previous sections. The other data will be a probability measure π with a smooth and positive density. But first let us consider another diffusion generator L (whose diffusion symmetric matrix field and drift vector field will be denoted ( a i,j (x)) i,j∈ 1,n and ( b i (x)) i∈ 1,n for x belonging to a chart C) satisfying the same conditions as L. A corresponding diffusion process is denoted ( X (µ) (t)) t≥0 (instead of (Y (µ) (t)) t≥0 in the previous sections). Here is a preliminary condition for absolute continuity on finite time horizons:

Proposition 24 Let µ and µ be two initial distributions, if for some T > 0 we have L( X ( µ) ([0, T ])) L(X (µ) ([0, T ])) then on any chart C, we have

∀ x ∈ C, a(x) = a(x)

Proof

First we assume that µ = µ = δ x , the Dirac mass at x ∈ S and we consider C an open chart containing x. Let us show that in this chart, we have a(x) = a(x).

For i ∈ 1, n , we denote by x i the i th coordinate mapping in C centered in x (namely

x i (x) = 0 for all i ∈ 1, n ). Let (v i ) i∈ 1,n ∈ R n be a given vector and consider C an open set of S satisfying x ∈ C and C ⊂ C. It is possible to extend the mapping C x → i∈ 1,n v i x i into a function f ∈ C ∞ .
Since the martingale M (f ) associated to f is continuous, the iterated logarithm law (see for instance the book of Revuz and Yor [START_REF] Revuz | Continuous martingales and Brownian motion, volume 293 of Grundlehren der Mathematischen Wissenschaften[END_REF]) shows that a.s. lim sup

t→0 + M (f ) t M (f ) t ln(ln(1/ M (f ) t )) = 1
where according to Remark 9, the bracket M (f ) of the martingale M (f ) is given by

∀ t ≥ 0, M (f ) t = t 0 Γ[f ](X (δx) (s)) ds
We compute that on any chart C , the carré du champ Γ[f ] can be written down as

∀ y ∈ C , Γ[f ](y) = i,j∈ 1,n a i,j (y)∂ i f (y)∂ j f (y)
In particular, since a.s. lim t→0 + X (δx) (t) = x, it follows that as t goes to zero,

M (f ) t ∼ t i,j∈ 1,n a i,j (x)v i v j = tv t a(x)v
and we get that a.s., lim sup

t→0 + f (X (δx) (t)) t ln(ln(1/t)) = lim sup t→0 + M (f ) t t ln(ln(1/t)) = v t a(x)v
Similarly we have a.s.

lim sup t→0 + f ( X (δx) (t)) t ln(ln(1/t)) = v t a(x)v
so we deduce that for any vector v ∈ R n ,

v t a(x)v = v t a(x)v
Since a(x) and a(x) are symmetrical, this relation implies that a(x) = a(x).

More generally, for any initial distributions µ and µ, the above arguments show that for any function f ∈ C ∞ , we have a.s., lim sup

t→0 + f (X (µ) (t)) t ln(ln(1/t)) = Γ[f ](X (µ) (0)) lim sup t→0 + f ( X ( µ) (t)) t ln(ln(1/t)) = Γ[f ](X ( µ) (0))
Assume now that the support of µ is the whole state space S and that the conclusion of the above proposition is not satisfied. Then we can find a chart C, a point x 0 ∈ C and a vector v ∈ R n such that η = β -β = 0, where β v t a(x 0 )v and β v t a(x 0 )v. Let f ∈ C ∞ be a function as above which coincides with x → i∈ 1,n v i x i on a neighborhood C ⊂ C of x 0 . Then we can find another neighborhood C ⊂ C such that for any x ∈ C ,

|Γ[f ](x) -β| ≤ η/3 Γ[f ](x) -β ≤ η/3
Assume for instance that β > β and consider in the space of continuous trajectories from [0, T ] to S the event

E X(0) ∈ C , lim sup t→0 + f (X(t)) t ln(ln(1/t)) ≤ β + β 2
where (X(t)) t∈[0,T ] is the canonical coordinate process. Then under L(X (µ) ([0, T ])), E is negligible while it has probability µ(C ) > 0 under L( X ( µ) ([0, T ])) and this is contradictory with our absolute continuity assumption. So the conclusion of the above proposition also holds if the support of µ is S.

Finally we consider the general case for the initial distributions µ and µ. Due to the compactness of S and our assumption on the diffusive matrix fields, the operator L is uniformly elliptic, so for T > 0 the law µ T /2 of X (µ) T /2 admits a smooth and positive density and in particular its support is S. Thus applying the above arguments to L(X (µ) ([T /2, T ])) and L( X ( µ) ([T /2, T ])) we get the announced conclusion, at least if we know that L( X ( µ) ([T /2, T ]))

L(X (µ) ([T /2, T ])). But this is an immediate consequence of the assumption L( X ( µ) ([0, T ]))

L(X (µ) ([0, T ])).

Since in the end we will mainly be interested into diffusions ( X (µ) t ) t≥0 which are absolutely continuous with respect to (X (µ) t ) t≥0 on finite time horizons, we see that the diffusive matrix field of L will have to coincide with that of L. This leads us to consider the corresponding Riemannian structure.

For x ∈ S, we introduce a scalar product •, • (x) on the tangent space T x S of S at x: if v, w ∈ T x S and if C is a chart with x ∈ C, we define v, w (x) i,j∈ 1,n (a -1 (x)) i,j v i w j where (v i ) i∈ 1,n and (w i ) i∈ 1,n are the coordinates of v and w in the chart C. It can be checked that ( •, • (x)) x∈S satisfies the rules of 2-covariant tensor and since it is symmetrical and positive definite, it gives rise to a Riemannian structure on S, see for instance the book of Ikeda and Watanabe [START_REF] Ikeda | Stochastic differential equations and diffusion processes[END_REF]. From now on, we denote by •, • , |•|, ∇, div, and λ, respectively the scalar product, the norm, the gradient, the divergence, the Laplacian and the probability associated to this Riemannian structure. The operator L can then be rewritten under a more intrinsic way:

L• = /2 • + b, ∇• (15)
where b is a vector field on S (but whose coordinates (b i ) i∈ 1,n in a chart don't necessary coincide with those given in the formulation [START_REF] Ikeda | Stochastic differential equations and diffusion processes[END_REF]). Assuming that a = a, the other generator L can be written under the same form, L• = /2 • + b, ∇• , with another vector field b. The usual Girsanov formula can now be stated as:

Proposition 25 For any initial distribution µ and any finite time horizon T ≥ 0, the law L( X (µ) ([0, T ])) is absolutely continuous with respect to L(X (µ) ([0, T ])) and the corresponding Radon-Nikodym density is equal to

L( X (µ) ([0, T ])) L(X (µ) ([0, T ])) = exp M ( b-b) T - 1 2 T 0 b -b 2 (X (µ) (t)) dt where (M ( b-b) t
) t≥0 is a martingale whose bracket is given by

∀ t ≥ 0, M ( b-b) t = t 0 b -b 2 (X (µ) (s)) ds
This result can be proven by an approach formally similar to that of section 2. Indeed, if F is a smooth function on S 2 such that

∀ x ∈ S, ∇ y F (x, y) |y=x = b(x) -b(x)
then with the notations of section 2, M ( b-b) corresponds to M (F ) (see also Remark 14). The definition of the martingales associated to functions of two variables goes through an approximation procedure, starting with simple functions of the kind F = f ⊗ g, with f, g ∈ C ∞ , for which we take

∀ t ≥ 0, M (F ) t t 0 f (X (µ) (s-)) dM (g) s ( 16
)
The completion of the vector space generated by functions of the form F = f ⊗ g, with f, g ∈ C ∞ , is done with respect to the semi-norm ||| • ||| on C ∞ (S 2 ) defined by

∀ F ∈ C ∞ (S 2 ), |||F ||| sup x∈S Γ[F (x, •)](x) (17)
where Γ is the carré du champ associated to L (acting on the second variable in the above formula).

In the diffusion framework the computation of the Radon-Nikodym densities are even easier, for instance the martingale

(E t [ b -b]) t≥0 exp M ( b-b) t - 1 2 t 0 b -b 2 (X (µ) (s) ds t≥0 (18)
is the Doléans-Dade exponential of the martingale M ( b-b) , namely the solution of the s.d.e.

E 0 [ b -b] = 1 ∀ s ≥ 0, dE s [ b -b] = E s-[ b -b] dM ( b-b) s
(in the diffusion setting, the s-(indicating left limit) in the above formula and in ( 14) can be replaced by s). But for our restricted purposes here, it is not necessary to developp this approach (this is done in a general setting in [START_REF] Miclo | An introduction to Markov processes[END_REF]) and we resort to a more traditional point of view:

Proof of Proposition 24

To construct directly the martingale M ( b-b) , we imbed S isometrically into R N via the Nash's theorem (see for instance the book of Han and Hong [START_REF] Han | Isometric embedding of Riemannian manifolds in Euclidean spaces[END_REF]). Let (e i ) i∈ 1,N be the canonical basis of R N . For each i ∈ 1, N and x ∈ S, we denote v i (x) ∈ T x S the orthogonal projection of e i on the vector space T x S (seen as a vector subspace of the Euclidean space R N ). If X (µ) (0) is given and distributed according to µ on S and if ((W i (t)) t≥0 ) i∈ 1,N is a family of independent standard one-dimensional Brownian motions (furthermore independent from X (µ) (0)), it is well-known that the solution (X (µ) (t)) t≥0 of s.d.e.

∀ t ≥ 0, dX (µ) (t) = i∈ 1,N v i (X (µ) (t)) dW i (t) + b(X (µ) (t)) dt
stays in S and that its law is solution to the martingale problem associated to µ and L. Indeed, using Itô's formula we get that for any

f ∈ C ∞ , f (X (µ) (t)) = f (X (µ) (0)) + t 0 L[f ](X (µ) (s)) ds + M (f ) t
where M (f ) is the martingale defined by

∀ t ≥ 0, M (f ) t i∈ 1,N t 0 v i (X (µ) (s)) dW i (s) Now we define the martingale M ( b-b) by ∀ t ≥ 0, M ( b-b) t i∈ 1,N t 0 b -b, v i (X (µ) (s)) ds
and we compute that its bracket is given by

∀ t ≥ 0, M ( b-b) t i∈ 1,N t 0 b -b, v i 2 (X (µ) (s)) ds = i∈ 1,N t 0 ( b -b)(X (µ) (s)), e i 2 ds = t 0 b -b 2 (X (µ) (s)) ds
Since the martingale M ( b-b) is continuous, we deduce that the process E[ b -b] defined in ( 16) is a positive martingale starting from 1. Thus via Kolmogorov's theorem, we can use it to construct a probability measure P µ on the σ-algebra generated by X (µ) by imposing that on σ(X

(µ) t : t ∈ [0, T ]), d P µ /dP µ = E T [ b -b], for any T ≥ 0.
Next for any function f ∈ C ∞ , we get the co-bracket of M ( b-b) and M (f ) by a similar computation:

∀ t ≥ 0, M ( b-b) , M (f ) t i∈ 1,N t 0 b -b, v i (X (µ) (s)) ∇f, v i (X (µ) (s)) ds = t 0 b -b, ∇f (X (µ) (s)) ds
It follows that the process

M (f ) t - t 0 b -b, ∇f (X (µ) (s)) ds E t [ b -b] t≥0
is a martingale under P µ , fact which is immediately translated into the assertion that the process M (f ) defined by

∀ t ∈ R + , M (f ) t M (f ) t - t 0 b -b, ∇f (X (µ) (s)) ds = f (X (µ) (t)) -f (X (µ) (0)) - t 0 L[f ](X (µ) (s)) ds
is a martingale under P µ . Thus the image of P µ under the process X (µ) is the solution to the martingale problem associated to µ and L and the validity of the above proposition follows.

This absolute continuity property enables to obtain a converse result to Proposition 23:

Remark 26 By conditioning with respect to X (µ) (0) and applying Proposition 24 with µ a Dirac mass, we get the equivalence between the following asertions:

• We have µ µ and a = a. • There exists T > 0 such that L( X

( µ) ([0, T ])) L(X (µ) ([0, T ])). • For any T ≥ 0, we have L( X ( µ) ([0, T ])) L(X (µ) ([0, T ])).
Furthermore in this situation, the Radon-Nikodym density is given, for any T ≥ 0, by

L( X ( µ) ([0, T ])) L(X (µ) ([0, T ])) = d µ dµ (X (µ) (0)) exp M ( b-b) T - 1 2 T 0 b -b 2 (X (µ) (t)) dt
These results lead us to introduce the notation L ∼ L, where L and L are two generators as in the beginning of this section, if a = a (by analogy with the previous section, we could also have adopted the notation L L, but we prefered to write L ∼ L to indicate that in the present continuous framework, this is an equivalence relation). Let π be a probability measure on S. We define an associated discrepancy d on the set L of generators as above by

∀ L, L ∈ L, d( L, L) b -b 2 (x) π(dx) , if L ∼ L +∞ , otherwise
Note that the discrepancy d is symmetrical: for any L, L ∈ L, d( L, L) = d(L, L).

To justify the introduction of d (and to try to smooth the abuse of notation consisting in denoting it in the same way as the distance of Billera and Diaconis [START_REF] Billera | A geometric interpretation of the Metropolis-Hastings algorithm[END_REF] in the discrete time and space setting), let us consider ϕ : R + → R a convex function differentiable in a neighborhood of 1, admitting a second derivative ϕ (1) > 0, satisfying ϕ(1) = ϕ (1) = 0 and whose growth is at most of polynomial order. Then we have a result analogous to Proposition 5:

Proposition 27 For any L, L ∈ L, we have lim

T →0 + Ent ϕ (L( X (π) ([0, T ]))|L(X (π) ([0, T ])))/T = ϕ (1) 2 d( L, L)
As it will appear in the following proof, this convergence is also true if ϕ (1) = 0, but we have to replace ϕ (1)d( L, L) by 0 if L ∼ L and +∞ otherwise.

Proof

If the condition L L is not satisfied, then according to Remark 25 we have

∀ T > 0, Ent ϕ (L( X (π) ([0, T ]))|L(X (π) ([0, T ]))) = +∞
Thus it is sufficient to treat the situation where L ∼ L. According to Proposition 24, we have for any

T ≥ 0, Ent ϕ (L( X (π) ([0, T ]))|L(X (π) ([0, T ]))) = E ϕ(E T [ b -b])
As in the finite state space, this expectation is finite because for any T ≥ 0 and p ≥ 1, we have

E E p T [ b -b] = E exp pM ( b-b) T - p 2 T 0 b -b 2 (X (µ) (t)) dt (19) = E E T [p( b -b)] exp p 2 -p 2 T 0 b -b 2 (X (µ) (t)) dt ≤ exp p 2 -p 2 T b -b 2 ∞ E E T [p( b -b)] = exp p 2 -p 2 T b -b 2 ∞
We begin by assuming furthermore that ϕ is smooth on R + and that the growth of ϕ is at most of polynomial order. In this case we can use directly Itô's formula to get that for any T ≥ 0,

E ϕ(E T [ b -b]) = E T 0 ϕ (E t [ b -b])E t [ b -b] dM ( b-b) t + 1 2 T 0 ϕ (E t [ b -b])E 2 t [ b -b] d M ( b-b) t = 1 2 E T 0 ϕ (E t [ b -b])E 2 t [ b -b] b -b 2 (X (π) (t)) dt = 1 2 T 0 E ϕ (E t [ b -b])E 2 t [ b -b] b -b 2 (X (π) (t)) dt
So if we divide by T and let T go to zero, we get in the limit

1 2 E ϕ (E 0 [ b -b])E 2 0 [ b -b] b -b (X (π) (0)) = ϕ (1) 2 d( L, L)
where to justify the convergence, we have taken into account the fact that the growth of ϕ is at most of polynomial order and the bound [START_REF] Saloff-Coste | Lectures on finite Markov chains[END_REF]. Note that the convexity of ϕ was not necessery to deduce this convergence. We now come to the general case. By our assumptions on ϕ, for any > 0, we can find two smooth functions ϕ ,-and ϕ ,+ on R + satisfying the following conditions:

ϕ ,-(0) = ϕ ,-(0) = 0 = ϕ ,+ (0) = ϕ ,+ (0) ϕ ,-(0) = ϕ (0) - and ϕ ,+ (0) = ϕ (0) + ∀ s ∈ R + , ϕ -, (s) ≤ ϕ(s) ≤ ϕ +, (s)
ϕ -, and ϕ +, grow at most polynomially Then using the previous convergence with the functions ϕ ,-and ϕ ,+ and the following bound valid for any T ≥ 0,

E ϕ -, (E T [ b -b]) ≤ Ent ϕ (L( X (π) ([0, T ]))|L(X (π) ([0, T ]))) ≤ E ϕ +, (E T [ b -b])
it appears that lim sup

T →0 + Ent ϕ (L( X (π) ([0, T ]))|L(X (π) ([0, T ]))) T ≤ ϕ (0) + lim inf T →0 + Ent ϕ (L( X (π) ([0, T ]))|L(X (π) ([0, T ]))) T ≥ ϕ (0) -
It remains to let go to zero to be convinced of the announced convergence.

In the case of the usual entropy, corresponding to the function R + s → u ln(u) -u + 1, we recover the analogous result to Proposition 3: if π is invariant for L, then for any T ≥ 0, we have

Ent(L( X (π) ([0, T ]))|L(X (π) ([0, T ]))) = T 2 d( L, L) ≤ +∞
Indeed, the only nontrivial case corresponds to T > 0 and L L, for which we compute that

∀ T > 0, Ent(L( X (π) ([0, T ]))|L(X (π) ([0, T ]))) = E π ln E T [ b -b] = E π M ( b-b) T - 1 2 T 0 b -b 2 ( X (π) (t)) dt
where E π [•] stands for the expectation with respect to X (π) . To go further, note that M ( b-b) is no longer a martingale under this law and to transform it into a martingale we have to substract the process M ( b-b) , M ( b-b) (this comes from arguments similar to those used in the proof of Proposition 24, see also the book [START_REF] Revuz | Continuous martingales and Brownian motion, volume 293 of Grundlehren der Mathematischen Wissenschaften[END_REF] of Revuz and Yor). Thus it follows that Thus as it was announced, the discrepancies 2 d and d ϕ for ∈ (0, 1/2] all coincides with d in our diffusion framework. It is then quite natural to propose as the Metropolis generator associated to π and L, the minimizer L d of the mapping L(π) L → d( L, L), at least if it exists. Here L(π) also stands for the set of generators from L ∈ L for which π is reversible. This means that

∀ f, g ∈ C ∞ , π[f L[g]] = π[g L[f ]]
Under our smoothness assumptions, for a given L ∈ L, if such a reversible probability measure π exists, it admits a positive and smooth density with respect to λ, because π must also be invariant for L and so it is a weak solution to the elliptic equation L * [π] = 0, where L * is dual operator of L in L 2 (λ). Conversely, if π is a probability measure admitting a positive and smooth density with respect to λ, then L(π) is not empty, since it contains at least the operator ( • + ∇ ln(π), ∇• )/2.

In fact let us check that this is the only element L of L(π) satisfying L ∼ L, where L is given in [START_REF] Jun | Monte Carlo strategies in scientific computing[END_REF]. The condition L ∼ L implies that there exists a vector field b such that we can write L• = 1 2

• + b, ∇• . The dual operator L * of L in L 2 (λ) is then given by L * • = 1 2

• -div(• b). The reversibility of π with respect to L is equivalent to the fact that L is equal to its dual operator in L 2 (π), condition which can be written

L• = 1 π L * [π•] (20)
(where we denote in the same way the probability measure π and its density with respect to λ).

By expanding this relation and by taking into account the equation L * [π] = 0, we get that the vector field ∇π π -2 b must vanish everywhere, which amounts to the above assertion. So the minimization of L(π) L → d( L, L) is very simple, since L d ( • + ∇ ln(π), ∇• )/2 is the unique element of L(π) with d(L d , L) < +∞.

The above approach can be extended to the situation where we add jumps to the above diffusion generators. But as already mentioned in the discussion after Proposition 24, we don't want to developp here the underlying theory of martingales associated to functions of two variables. So let us close this paper by sketching the line of reasoning, which is a mix of the arguments given in the finite and diffusion case, without entering into the details of the corresponding computations:

Remark 28 Consider generators of the type H = L + Q, where the diffusion part L is given as in [START_REF] Ikeda | Stochastic differential equations and diffusion processes[END_REF], with the same assumptions on the coefficients a and b, and where the jump part can be written as

∀ f ∈ C ∞ , ∀ x ∈ S, Q[f ](x) (f (y) -f (x)) q(x, y)λ(dy)
where the intensity of jumps q is a positive and smooth function on S 2 . It is easy to see that the decomposition of H under the form L + Q is unique and more precisely that the action of H on C ∞ determine the coefficients a, b (in any chart) and q. The set of such generators H will be denoted H.

If µ is a probability measure on S, we denote (X (µ) ) t≥0 any càdlàg Markov process admitting µ as initial distribution and H as generator. Its law on the set of càdlàg trajectories is the unique solution of the martingale problem associated to µ and H.

Let H ∈ H be another generator of the same kind, all notions relative to H will receive a tilde at their top. As in the beginning of this section, for any T > 0, we have L( X (µ) ([0, T ]) L(X (µ) ([0, T ]) if and only if a = a, property which is still denoted by H ∼ H. Again we endow S with the Riemannian structure induced by a -1 , in order to adopt intrinsic notations:

H = /2 • + b, ∇• + Q[•]
, where b is a vector field on S (and idem for H if H ∼ H). Let us introduce the functions V and v defined by ∀ (x, y) ∈ S 2 , V (x, y) ln q(x,y) q(x,y)

, if x = y 0 , if x = y ∀ x ∈ S, v(x) (V (x, y) -exp(V (x, y)) + 1)q(x, y) λ(dy)

Then it is possible to associate naturally to V a martingale M (V ) , such that if H ∼ H, we have for any T ≥ 0,

L( X (µ) ([0, T ])) L(X (µ) ([0, T ])) = E T [ b -b]E T [V ]
where the first factor was defined in [START_REF] Revuz | Continuous martingales and Brownian motion, volume 293 of Grundlehren der Mathematischen Wissenschaften[END_REF] and the second factor is given by

E T [V ] exp M (V ) T + T 0 v(X (µ) (t)) dt
The fact that these densities so neatly decompose into a diffusion factor and a jump factor is related to the fact that the martingale M (V ) is totally discontinuous (namely its co-bracket with any continuous martingale is null, see for instance the book of Dellacherie and Meyer [START_REF] Dellacherie | Probabilités et potentiel. Chapitres V à VIII[END_REF]). So in this situation, we see that in the completion of the space of simple functions of two variables with respect to the norm [START_REF] Miclo | An introduction to Markov processes[END_REF], two kinds of orthogonal objects appear: germs of functions on the diagonal (corresponding to vector fields) and functions of two variables which vanish on the diagonal (corresponding to jump rate densities). The parametrization of Girsanov transformations by these objects (the couple ( b -b, V ) in the above example) is in fact very general, as it was alluded to in Remark 14. These formulas enable to handle ϕ-entropies of trajectorial laws and to define corresponding discrepancies. Indeed, under the assumptions on ϕ preceding Proposition 26, we get for any probability measure π on S, (x) π(dx) + ϕ q(x,y) q(x,y) π(dx)q(x, y)λ(dy) , if H ∼ H +∞ , otherwise Assume now that π has a smooth and positive density with respect to λ (which will still be denoted π) and consider H(π) the subset of H consisting of generators from H admitting π as a reversible measure. As it can be guessed, our purpose is to find the minimizer H ϕ of the mapping H(π) H → d ϕ ( H, H), under the additional condition on ϕ given in Proposition 20. In order to go in this direction the following result is important.

Proposition 29

The generator H is reversible with respect to π if and only if its diffusion part L and its jump part Q are both reversible with respect to π.

Proof

As in the case (18) of the diffusion generators, the reversibility of π is equivalent to the equation

H• = 1 π H * [π•]
, where H * is the dual operator of H in L 2 (λ). Expanding the r.h.s. we get that for any f ∈ C ∞ and x ∈ S,

1 π(x)
H * [πf ](x) = 1 2 f (x) + ∇ ln(π) -b, ∇f (x) + (f (y) -f (x)) π(y) π(x) q(y, x)λ(dy)

+ H * [π] π(x) f (x)

Proposition 3

 3 x∈S π(x)M (x, y) = 0 If π is invariant for M , for any T ≥ 0, we haveEnt(L(Y (π) ([0, T ]))|L(X (π) ([0, T ]))) = T d(M, L) ≤ +∞where d is the discrepancy defined by ∀ M, M ∈ L, d(M , M ) x∈S π(x) y∈S\{x} M (x, y) ln M (x, y) M (x, y) -M (x, y) + M (x, y)

Theorem 8

 8 Under the assumption that L L, for any initial condition µ and any finite time horizon T ≥ 0, we have P µ,[0,T ] P µ,[0,T ] and the corresponding Radon-Nikodym derivative is given by d P µ,[0,T ] dP µ,[0,T ] these quantities vanish if N (x,y) T

  We are led to minimize as a function of α ≥ 0 the expression 2(α ln(α) -α) -α ln(ββ ) + β + β By differentiating this strictly convex function, we see that the unique minimizer is α * √ ββ . The announced results follow at once. Due to the fact that ∀ a, b ∈ R + , min(a, b) ≤ √ ab we get that

  If π is reversible for M and M L, we can write d ϕ (M, L) = x≺y π(x)L(x, y)ϕ M (x, y) L(x, y) + π(y)L(y, x)ϕ M (y, x) L(y, x) = x≺y Φ π(x)L(x,y),π(y)L(y,x) (π(x)M (x, y))

  and consider the function ϕ , for which D -= {1} and D + = {1 + }. Thus the condition of Proposition 20 is fulfilled and the mapping L(π) M → d ϕ (M, L) admits a unique minimizer L ϕ ,π . Before proving the convergence (3), let us give a more precise version of Proposition 2. From now on, endow S with an order such that ∀ x, y ∈ S, x ≺ y ⇒ π(x)L(x, y) ≤ π(y)L(y, x) Then we have Proposition 22 A generator M ∈ L(π) is a minimizer of d(•, L) on L(π) if and only if for any x ≺ y, we have π(x)M (x, y) = π(y)M (y, x) ∈ [π(x)L(x, y), π(y)L(y, x)] Proof Consider the convex function ψ : R + u → |u -1|. If we replace the distance d by the discrepancy d ψ , which coincides with d on couples (M , M ) ∈ L 2 with M M and is equal to +∞ otherwise, the proof of the second part of Proposition 5 shows that a generator M ∈ L(π) is a minimizer of d ψ (•, L) on L(π) if and only if for any x ≺ y, with L(x, y)L(y, x) > 0, we have that π(x)M (x, y) is a minimizer of Ψ π(x)L(x,y),π(y)L(y,x) , where ∀ α, β, β ≥ 0, Φ β,β (α) |α -β| + α -β This function is easy to minimize and we find the condition π(x)M (x, y) ∈ [π(x)L(x, y), π(y)L(y, x)]

2 T 0 b -b 2 ( 2 T 0 E π b -b 2 ( 2 E π b -b 2 (

 20220222 Ent(L( X (π) ([0, T ]))|L(X (π) ([0, T ]))) = E π 1 X (π) (t)) dt = 1 X (π) (t)) dt = T X (π) (0))because π is invariant for L and we recognize the last term as T d( L, L)/2.

lim T →0 +

 →0 Ent ϕ (L( X (π) ([0, T ]))|L(X (π) ([0, T ])))/T = d ϕ ( L, L)where the discrepancy in the r.h.s. is given by d ϕ ( L, L)

So the previous equality is equivalent to the fact that

π(y) π(x) q(y, x) = q(x, y)

The second equation is equivalent to the reversibility of π with respect to the diffusion part L and the third equation is equivalent to the reversibility of π with respect to the jump part Q. The first equation, which is the formulation of the stationarity of π, is in fact implied by the two other equations.

Indeed, the last proposition is also true without assumpion of regularity on the probability measure π, but it appears a posteriori that π has to admit a smooth and positive density with respect to λ, since it must also be reversible for the elliptic operator L.

Thus H ϕ is a minimizer of the mapping H(π) H → d ϕ ( H, H) if and only if its diffusion part L ϕ is a minimizer of the mapping L(π) L → ϕ (1) 2 d( L, L) and its jump part Q ϕ is a minimizer of the mapping q → ϕ q(x,y) q(x,y) π(dx)q(x, y)λ(dy). For the diffusion part, this leads to L ϕ = ( • + ∇ ln(π), ∇• )/2. For the jump part, the computations of the proof of Proposition 5 (taking into account Proposition 20) lead to

where the function (R * + ) 2 (β, β ) → α β,β was defined in term of ϕ in the proof of Proposition 5. In particular in the case of the classical entropy, we find the rate density q given by ∀ x = y, q(x, y) = π(y) π(x) q(x, y)q(y, x)

Aknowledgments:

We are grateful to the ANR's Chaire d'Excellence program for providing financial support, as well as to the Laboratoire J. A. Dieudonné (UMR 6621) in Nice and to the Institut de Mathématiques (UMR 5219) in Toulouse, where parts of this work were done, for their hospitality.