Giovanni Conforti
email: giovanniconfort@gmail.com

Christian Léonard
email: christian.leonard@u-paris10.fr

Reciprocal classes of random walks on graphs

Keywords: 2010 Mathematics Subject Classification. 60J27, 60J75 Random walks on graphs, bridges of random walks, reciprocal characteristics, Schrödinger problem

The reciprocal class of a Markov path measure is the set of all mixtures of its bridges. We give characterizations of the reciprocal class of a continuous-time Markov random walk on a graph. Our main result is in terms of some reciprocal characteristics whose expression only depends on the jump intensity. We also characterize the reciprocal class by means of Taylor expansions in small time of some conditional probabilities.

Our measure-theoretical approach allows to extend significantly already known results on the subject. The abstract results are illustrated by several examples.

Introduction

This article answers the question: "When does a continuous-time random walk on a graph share its bridges with a given Markov walk?", both in terms of their jump intensities and of Taylor expansions in small time of probabilities of conditioned events. The precise answers are stated at Theorem 2.4 and Corollary 2.6 which are the main results of the article.

The set of all path measures which share the bridges of a given Markov measure is called its reciprocal class. In contrast with most of the existing literature about reciprocal classes, i.e. shared bridges, which relies on transition probabilities, in this paper we adopt a measure-theoretical approach: our main objects of interest are path measures, i.e. probability measures on the path space, rather than transition probability kernels. It turns out that this is an efficient way for solving our problem and allows to extend significantly already known results on the subject.

Notation. Some notation is needed before bringing detail about the above question and its answers. For any measurable space Y, P(Y ) denotes the set of all probability measures on Y. We denote the support of a probability measure p by supp p. On a discrete space A, we have supp p = {a ∈ A : p(a) > 0} and for any probability measures p and q, p is absolutely continuous with respect to q : p q, if and only if supp p ⊂ supp q. The support of a function u ∈ R A is defined as usual by supp u := {a ∈ A : u(a) = 0} . Functions with a finite support will be useful to define Markov generators without extra assumptions on the jump intensity.

We consider random walks from the unit time interval [0, 1] to a countable directed graph (X , A → ) where only jumps along the set A → ⊂ X 2 of the arcs of the graph are allowed. The set of all the sample paths is denoted by Ω ⊂ X [0,1] . As we adopt a measure theoretical viewpoint, it is worth identifying the random processes and their laws on the path space. Consequently, any path measure P ∈ P(Ω) is called a random walk. The canonical process on Ω is denoted as usual by (X t ; 0 ≤ t ≤ 1). For any random walk P ∈ P(Ω) we denote

• P 0 (dx) := P (X 0 ∈ dx) ∈ P(X ), its initial marginal;

• P 01 (dxdy) := P (X 0 ∈ dx, X 1 ∈ dy) ∈ P(X 2 ), its endpoint marginal;

• P x := P (• | X 0 = x) ∈ P(Ω), the random walk conditioned to start at x ∈ supp P 0 ;

• P xy := P (• | X 0 = x, X 1 = y) ∈ P(Ω), its xy-bridge with (x, y) ∈ supp P 01 .

Aim of the article. We take some Markov random walk R ∈ P(Ω) with the jump intensity j : [0, 1] × A → → [0, ∞) and we assume that its initial marginal R 0 ∈ P(X ) has a full support. This random walk is our reference path measure.

For comparison with the results of this article, let us consider for a little while the set M(j) := x∈X µ 0 (x) R x ; µ 0 ∈ P(X ) ⊂ P(Ω), assuming that for any x, R x is uniquely well defined. Obviously, for any P ∈ P(Ω), the three following statements are equivalent:

(1) P ∈ M(j);

(2) P x = R x , for all x ∈ supp P 0 ;

(3) For any x ∈ supp P 0 , P x is Markov with intensity j.

Rather than the collection of all the random walks R x conditioned by their starting point x ∈ X , our interest is in the bridges of R. We define R(j) :=

x,y∈X π(x, y) R xy ; π ∈ P(X 2 ) : supp π ⊂ supp R 01 ⊂ P(Ω)

(1) to be the convex hull of all these bridges. This set is called the reciprocal class of the intensity j. Since the reference random walk R is Markov, so are its bridges R xy . But, in general a mixture of such bridges fails to remain Markov. However, any element P of R(j) still satisfies the reciprocal property which extends the Markov property in the following way.

Definition 0.1 (Reciprocal walk). A random walk P ∈ P(Ω) is said to be a reciprocal walk if for any 0

≤ u ≤ v ≤ 1, P (X [u,v] ∈ • | X [0,u] , X [v,1] ) = P (X [u,v] ∈ • | X u , X v ).
The reciprocal property of a path measure is defined in accordance with the usual notion related to processes. Basic material about reciprocal walks is collected at Appendix A.

We see clearly that for any P ∈ P(Ω), the two following statements are equivalent:

(1)' P ∈ R(j);

(2)' P xy = R xy , for all (x, y) ∈ supp P 01 . The aim of the article is to provide an analogue of statement (3) above. Indeed, Theorem 2.4 states that (1)' and (2)' are equivalent to

(3)' For any x ∈ supp P 0 , P x is Markov and

χ [P x ] = χ [j], (2)
where for any random walk P , χ [P ] = χ [k] only depends on the intensity k of P and is described at Definition 2.3. For this reason, χ [j] is called the characteristic of the reciprocal class R(j).

Markov or not Markov? There are other random walks P than R in R(j) that are Markov. In this case, the intensities (k x ; x ∈ supp P 0 ) are such that k x does not depend on x. When k x depends explicitly on x, P is not Markov; this is the case for most of the elements of R(j).

Variational processes. Besides the interest in its own right of the description of the convex hull of the bridges of some Markov dynamics, there exists a stronger motivation for investigating the reciprocal class of a Markov process. Suppose that you observe two large samples of non-interacting particle systems with two distinct endpoint distributions (i.e. empirical measures of the couples of initial and final positions). Are these two random systems driven by the same force field? In mathematical terms, you want to know if the dynamics that drive these two particle systems belong to the same reciprocal class. This question is rooted into a problem addressed by Schrödinger in the early 30's in the articles [START_REF] Schrödinger | Über die Umkehrung der Naturgesetze[END_REF][START_REF] Schrödinger | Sur la théorie relativiste de l'électron et l'interprétation de la mécanique quantique[END_REF].

Schrödinger problem. Consider a large number N of independent particles labeled by 1 ≤ i ≤ N and moving according to some Markov dynamics described by the reference path measure R ∈ P(Ω). In Schrödinger's papers, R is the law of a Brownian motion on X = R n and Ω = C([0, 1], R n ). Suppose that at time t = 0, the particles are distributed according to a profile close to some distribution µ 0 ∈ P(X ). In modern terms, this means that the empirical measure 1 N 1≤i≤N δ X i (0) of the initial sample is weakly close to µ 0 , where δ a is the Dirac measure at a and t → X i (t) describes the random motion of the i-th particle. Suppose that at time t = 1 you observe that the whole system is such that its distribution profile 1 N 1≤i≤N δ X i (1) is weakly close to some µ 1 ∈ P(X ) far away from the expected profile µ 0 e L ∈ P(X ) which is predicted by the law of large numbers. Here, L is the Markov generator of R. Schrödinger asks what is the most likely trajectory of the whole particle system conditionally on this very rare event. As translated in modern terms by Föllmer in [START_REF] Föllmer | Random fields and diffusion processes[END_REF] using large deviations technics, the empirical measure 1 N 1≤i≤N δ X i weakly tends in P(Ω) to the unique solution of entropy minimization problem

H(P |R) → min; P ∈ P(Ω) : P 0 = µ 0 , P 1 = µ 1 , (3)
where H(P |R) := E P log(dP/dR) ∈ [0, ∞] is the relative entropy of P with respect to the reference measure R. A recent review of the Schrödinger problem is proposed in [START_REF] Léonard | A survey of the Schrödinger problem and some of its connections with optimal transport[END_REF].

A stochastic analogue of Hamilton's principle. In the case where R is a Brownian motion, any P ∈ P(Ω) with H(P |R) finite is the solution of a martingale problem associated with some adapted drift field β P such that

E P [0,1] |β P t | 2 dt < ∞ and H(P |R) = E P [0,1] |β P t | 2 /2 dt. As |β P t | 2 /2 is a kinetic energy, H(P |R) is an average kinetic action
and the minimization problem (3) appears to be a stochastic generalization of the usual Hamilton variational principle, see for instance [START_REF] Léonard | A survey of the Schrödinger problem and some of its connections with optimal transport[END_REF] and the references therein.

A natural extension of Schrödinger's problem. Schrödinger's problem (3) also admits the following natural extension H(P |R) → min; P ∈ P(Ω) :

P 01 = π (4)
with π ∈ P(X 2 ) a prescribed endpoint distribution. In some sense, the entropy minimization problem (4) is the widest stochastic extension of the classical Hamilton least action principle.

The connection with the reciprocal class R[j]. To see the connection with the bridges of R, let us go back to our discrete set of vertices X and note that both Schrödinger's problem (3) with the prescribed marginals µ 0 = δ x and µ 1 = δ y and problem (4) with π = δ (x,y) , admit the unique solution

P = R xy .
This is a simple consequence of the additive decomposition formula

H(P |R) = H(P 01 |R 01 ) + x,y∈X P 01 (x, y)H(P xy |R xy )
applied with P 01 = δ (x,y) . One can interpret the bridge R xy as the stochastic analogue of a minimizing geodesic between x and y. We also see with the additive decomposition formula that the unique solution of (4) with a general endpoint distribution π ∈ P(X 2 ) such that H(π|R 01 ) < ∞ is

P = x,y∈X π(x, y) R xy .
Therefore, the reciprocal class R(j) appears to be essentially the set of all solutions of the stochastic variational problem (4) when π ∈ P(X 2 ) describes all possible endpoint distributions. In addition, we see with (2) that all bridges of R satisfy

χ [R xy ] = χ [j], ∀(x, y) ∈ supp R 01 .
This indicates that the reciprocal characteristic χ [j] encrypts the underlying stochastic Lagrangian associated with the stochastic action minimization problem (4). This point of view is developed in a diffusion setting by Zambrini and the second author in [LZ]. It will be explored in the present setting of random walks on graphs in a forthcoming paper.

At the present time very little is known about the solutions of the variational problems (3) and (4) in the setting of random walks on graphs. This paper is a contribution in this direction.

Literature. One year after Schrödinger's article [START_REF] Schrödinger | Über die Umkehrung der Naturgesetze[END_REF], Bernstein introduced in [START_REF] Bernstein | Sur les liaisons entre les grandeurs aléatoires[END_REF] the reciprocal property as a notion that extends Markov property and is respectful of the time reversal symmetry. It was further developed four decades later by Jamison [START_REF] Jamison | Reciprocal processes[END_REF][START_REF] Jamison | The Markov processes of Schrödinger[END_REF]. Relying on Jamison's approach to reciprocal processes, Clark proved in [START_REF] Clark | A local characterization of reciprocal diffusions[END_REF] a conjecture of Krener [START_REF] Krener | Reciprocal diffusions and stochastic differential equations of second order[END_REF] who proposed a characterization of the reciprocal class of a Brownian diffusion process in terms of an identity of the type χ [β P ] = χ [0] where β P is the drift of the Markov diffusion process P (recall the discussion below Eq. (3) for the notation β P ). Clark called χ [β P ] a reciprocal invariant. In the present article, we prefer naming "reciprocal characteristics" the analogous quantities χ [k].1 In view of the previous discussion about variational processes, it is not surprising that the reciprocal characteristics play a distinguished role when looking at reciprocal processes as solutions of second order stochastic differential equations. This is investigated by Krener, Levy and Thieullen in [START_REF] Krener | Dynamics and kinematics of reciprocal diffusions[END_REF][START_REF] Thieullen | Second order stochastic differential equations and non-gaussian reciprocal diffusions[END_REF][START_REF] Krener | Reciprocal diffusions in flat space[END_REF].

Characterization of reciprocal classes can also be stated in terms of stochastic integration by parts formulas, often called duality formulas. This was investigated by Roelly and Thieullen in [START_REF] Roelly | A characterization of reciprocal processes via an integration by parts formula on the path space[END_REF][START_REF] Roelly | Duality formula for the bridges of a Brownian diffusion: Application to gradient drifts[END_REF] for diffusion processes. In the specific context of counting random walks, this is done in [START_REF] Conforti | Bridges of Markov counting processes. Reciprocal classes and duality formulas[END_REF], a paper by Murr, Roelly and the authors of the present article. This was extended by Dai Pra, Roelly and the first author in [CDPR] for compound Poisson processes and in [CR] for random walks on Abelian groups. A main idea of [CDPR, CR] is to exploit the translation-invariant structure of the underlying graph to characterize the reciprocal classes through integration by parts formulas where the derivation measures the variation when adding a random closed walk to the canonical process, see [START_REF] Conforti | Reciprocal class of jump processes[END_REF]Thm. 3.3] and [START_REF] Conforti | Reciprocal class of random walks on an Abelian group[END_REF]Thm. 13]. In all these cases, reciprocal characteristics play a major role. If the graph is not assumed to be invariant with respect to some group transformations, such as translation-invariance and time homogeneity, there is no way of thinking of a natural differentiation. Since we do not assume any invariance in the present article, the integration by parts approach is not investigated.

It is worthwhile to note that, except for [START_REF] Roelly | A characterization of reciprocal processes via an integration by parts formula on the path space[END_REF] and the recent papers [CLMR15, CDPR, CR, LZ], in the whole literature on the subject, only the Markov members of the reciprocal class, that is the solutions of the original Schrödinger problem (3) as the marginal constraints vary, are characterized. In the present article, following a strategy close to [LZ]'s one, we give a characterization of the whole reciprocal class, that is the set of solutions of (4) as π varies, under very few restrictions on the reference random walk.

Outline of the paper. Next Section 1 is devoted to some preliminaries about directed graphs, Markov walks and their intensities. We also state our main hypotheses which are Assumption 1.1 and Assumption 1.5 and define carefully the reference path measure R. Our main results are stated at Section 2. They are Theorems 2.4 and 2.5, together with their Corollary 2.6. Theorem 2.4 is a rigorous version of statement (3)' while Theorem 2.5 provides an interpretation of the reciprocal characteristics in terms of Taylor expansions in small time of some conditional probabilities. Their proofs are done at Section 3. The key preliminary result is Lemma 3.2 whose proof is based on the identification of two expressions for the Radon-Nikodym derivative dP/dR of any element P of the reciprocal class with respect to the reference Markov measure R. Some more results about the elements of the reciprocal class are proved at Section 4. In particular, we give at Proposition 4.1 another characterization of R(j) in terms of the shape of the jump intensity of any element of the class. The characteristic equation (2) seen as an equation of the unknown P x where j is given is also solved at Theorem 4.2. Several examples are treated at Section 5. We have a look at: directed trees, birth and death processes, some planar graphs, the hypercube, the complete graph and some Cayley graphs. We calculate their reciprocal characteristics and in some cases solve the associated characteristic equation. Finally, there are appendix sections devoted to reciprocal random walks and to closed walks on a directed graph.

Preliminaries

This section is devoted to some preliminaries about directed graphs, Markov walks and their intensities. Our main hypotheses are stated below at Assumption 1.1 and Assumption 1.5. Much of the material in this section is required for the definition of the reciprocal characteristics and the statements of our results at Section 2.

Directed graph. Let X be a countable set. Any subset A ⊂ X 2 of the product space X 2 defines a structure of oriented graph on X by means of the relation → which is defined for all z, z ∈ X by z → z if and only if (z, z ) ∈ A . We denote (X , →) this directed graph, say that any (z, z ) ∈ A is an arc and write (z → z ) ∈ A instead of (z, z ) ∈ A .

Since (X , →) and A carry the same information, any subset of X 2 will called a directed graph. When we want to emphasize the role of the vertex set, we sometimes write (X , A ).

Assumption 1.1. The directed graph (X , →) satisfies the following requirements.

(1) It is locally finite, meaning that any vertex z ∈ X has finitely many neighbors, i.e. for all z ∈ X , the outer degree of z: deg(z

) := # {z ∈ X : z → z } , is finite. (2) It has no loops, meaning that (z → z) ∈ A for all z ∈ X .
Random walk on a graph. The countable set X is equipped with its discrete topology. We look at continuous-time random paths on (X , →) with finitely many jumps on the bounded time interval [0, 1]. The corresponding path space Ω ⊂ X [0,1] consists of all càdlàg piecewise constant paths ω = (ω t ) 0≤t≤1 on X with finitely many jumps such that ω 1 -= ω 1 and for all t ∈ (0, 1), ω t -= ω t implies that ω t -→ ω t . It is equipped with the canonical σ-field generated by the canonical process.

Definition 1.2. We call any probability measure on Ω a random walk on (X , →). This is not the customary usage, but it turns out to be convenient. As a probability measure, it specifies the behavior of a piecewise constant continuous-time random process that may not be Markov.

Notation related to random walks. As usual, the canonical process X = (X t ) t∈[0,1] is defined for each t ∈ [0, 1] and ω = (ω s ) 0≤s≤1 ∈ Ω by X t (ω) = ω t ∈ X . For any T ⊂ [0, 1] and any random walk P ∈ P(Ω), we denote X T = (X t ) t∈T and the push-forward measure P T = (X T ) # P. In particular, for any 0 ≤ t ≤ 1, P t = (X t ) # P ∈ P(X ) denotes the law of the position X t at time t and P 01 := P {0,1} denotes the law of the endpoint position (X 0 , X 1 ). Also, for all 0 ≤ r ≤ s ≤ 1, X [r,s] = (X t ) r≤t≤s and P [r,s] = (X [r,s] ) # P. We are mainly interested in bridges. In a general setting, one must be careful because the bridge P xy is only defined P 01 -almost everywhere. But in the present case where the state space X is countable, the kernel (x, y) → P xy is defined everywhere on supp P 01 , no almost-everywhere-precaution is needed when talking about bridges. In particular, any random walk P disintegrates as P = (x,y)∈supp P 01 P 01 (x, y)P xy ∈ P(Ω).

In the whole paper, the letters x and y are devoted respectively to the initial and final states of random walks. Current states are usually denoted by z, z ∈ X .

Markov walk. The Markov property of a path measure is defined in accordance with the usual notion related to processes.

Definition 1.3 (Markov walk). A random walk P ∈ P(Ω) is said to be a Markov walk if for any

0 ≤ t ≤ 1, P (X [t,1] ∈ • | X [0,t] ) = P (X [t,1] ∈ • | X t ).
A Markov walk P ∈ P(Ω) is the law of a continuous-time Markov chain with its sample paths in Ω. In our setting, all Markov walks to be encountered will be associated with some jump intensity2 k : [0, 1)×A → [0, ∞) which gives rise to the infinitesimal generator that acts on any real function u ∈ R X with a finite support via the formula

K t u(z) = z :z→z k(t, z → z ) (u z -u z ), z ∈ X , t ∈ [0, 1).
The random walk P ∈ P(Ω) is such that for any real function u ∈ R X with a finite support, the process u(X t ) -t 0 K s u(X s ) ds is a local P -martingale with respect to the canonical filtration. The average frequency of jump from z at time t is

k(t, z) := z :z→z k(t, z → z ).
(5)

Note that this is a finite number because it is assumed that (X , →) is locally finite. The sample paths of the random walk P admit a version in Ω if and only if k(t, z → z ) is t-measurable for all z and z and

[0,1) k(t, X t ) dt < ∞, P -a.s.
Indeed, this estimate means that the canonical process performs P -a.s. finitely many jumps.

In the situation where k doesn't depend on t, the dynamics of the random walk is described as follows. Once at site z, the walker waits during a random time with exponential law with parameter k(z) and then jumps onto z according to the probability measure k(z) -1 z :z→z k(z → z )δ z where δ z stands for the Dirac measure at z , and so on; all these random events being mutually independent.

Note that k(t, •) and K t are only defined for t in the semi-open interval [0, 1). The reason for this is that we are going to work with mixtures of bridges and the forward intensity of a bridge is singular at t = 1.

Directed subgraphs associated with an intensity. There are two relevant graph structures that are associated with the intensity k. The subgraph of k-active arcs at time t is the subset

A → (t, k) := {(z → z ) ∈ A : k(t, z → z ) > 0}
and its symmetric extension is denoted by

A ↔ (t, k) := {(z → z ), (z → z); (z → z ) ∈ A → (t, k)} .
Only Markov intensities such that these structures do not depend on time will be encountered, see (6) below.

Definitions 1.4 (The directed subgraphs associated to k). In the comfortable situation where A → (t, k) does not depend on t, i.e.

A → (t, k) = A → (k), ∀t ∈ [0, 1), (6)
A → (k) is called the subgraph of k-active arcs and A ↔ (k) denotes its symmetric extension.

The symmetrized subgraph will be necessary for considering closed walks.

Directed subgraphs associated with a random walk. Again P ∈ P(Ω) is a Markov random walk with an intensity k that satisfies (6). Since A (X , →) is assumed to be locally finite, and P -almost every sample path performs finitely many jumps, the assumption (6) implies that the support of P t ∈ P(X ) remains constant for each time 0 < t < 1. We denote this set by

X (P ) := supp P 1/2 ⊂ X .
It is the set of all vertices that are visited by the random walk P . Note that the initial and final times t = 0 and t = 1 are excluded to allow for P to be a bridge. We always have supp P 0 ⊂ X (P ) and supp P 1 ⊂ X (P ); these inclusions may be strict.

The directed subgraph (X (P ), A → (P )) of all P -active arcs is the subgraph of (X , A → (k)) which is defined by

A → (P ) := {(z → z ) ∈ A → (k) : z, z ∈ X (P )} .

Its symmetric extension is

A ↔ (P ) := {(z → z ), (z → z); (z → z ) ∈ A → (k), z, z ∈ X (P )} .
Let us provide some comment to make the relation between A → (k) and A → (P ) clearer. If the initial marginal P 0 is supported by a proper subset of X , it might happen that A → (P ) is a proper subset of A → (k) and also that A ↔ (P ) is a proper subset of A ↔ (k). For instance, let k be the intensity of the Poisson process on X = Z given by k(t, n → n + 1) = λ > 0 for all 0 ≤ t ≤ 1 and n ∈ Z. Let P be the Poisson random walk with intensity λ and initial state n 0 ∈ Z. Then,

A → (k) = {(n → n + 1); n ∈ Z} and A → (P ) = {(n → n + 1); n ∈ Z, n ≥ n 0 } .
The reference intensity and the reference random walk. We introduce a random walk R ∈ P(Ω) with jump intensity j. Both R and j will serve as reference path measure and intensity. We assume that A → (t, j) doesn't depend on time:

A → (t, j) = A → (j), ∀t ∈ [0, 1). (7)
We also suppose that A ↔ (j) = A and proj X A = X (8) where as a definition, for any

A ⊂ X 2 , proj X (A) := {z ∈ X : (z → z ) ∈ A for some z ∈ X } .
Although (7) is a restriction, when requiring (8) one doesn't loose generality since all random walks to be encountered later are absolutely continuous with respect to R. Note that this implies that (X , A ) is a symmetric directed graph. Similarly we denote A → (j) = A → to ease notation.

Assumption 1.5. The Markov jump intensity j : [0, 1] × A → [0, ∞) verifies the following requirements.

(1) The jump intensity j is such that the estimate

sup t∈[0,1],z∈X j(t, z) < ∞ (9)
holds where, as in (5), j(t, z) := z :z→z j(t, z → z ) stands for the average frequency of jump from z at time t.

(2) There is some subset A → of A such that all 0 ≤ t < 1, j(t, z → z ) > 0 for any (z → z ) ∈ A → and j(t, z → z ) = 0 for any (z → z ) ∈ A \ A → . This is another way for expressing (7).

(3) The intensity j is continuously t-differentiable, i.e. for any

(z → z ) ∈ A → the func- tion t → j(t, z → z ) is continuously differentiable on [0, 1].
The Assumption 1.5(1) implies that for each x ∈ X , there exists a unique solution

R x ∈ P(Ω)
to the martingale problem with initial marginal δ x associated with the generator L = (L t ) 0≤t≤1 defined for all finitely supported functions u by

L t u(z) = z :z→z j(t, z → z ) (u z -u z ), t ∈ [0, 1], z ∈ X .
For any x ∈ X , the bridges

R xy := R x (• | X 1 = y) of R x are well defined for all y ∈ supp R x 1 .
The reference random walk is defined by

R := x∈X R 0 (x) R x ∈ P(Ω)
where the initial marginal R 0 is any probability measure on X with a full support, i.e. supp R 0 = X .

Definitions 1.6 (About the j-active arcs from x to Y). Let x ∈ X be any vertex and Y be any nonempty subset of supp R x 1 . (a) We define the subgraph

A R → (x, Y) := ∪ y∈Y A → (R xy ) of all the arcs that constitute the A → -walks from x to Y. (b) We denote A R ↔ (x, Y) its symmetric extension. (c) We define the set X R (x, Y) := proj X A R → (x, Y
) of all vertices visited by the A → -walks starting at x and ending in Y.

Remark 1.7. Remark that {x} and Y may be proper subsets of X R (x, Y) as the example of a bridge R xy suggests in many situations. We also have for any P ∈ P(Ω),

({x} ∪ supp P x 1 ) ⊂ X (P x ) = proj X A → (P x )
where the inclusion may be strict.

Main results

Before stating the main results of the article, we still need to introduce two objects which are related to the notion of reciprocal walk, see Definition 0.1 for this notion.

Reciprocal class. The reciprocal class R(j) is defined at (1). It is the main object of our study. Remark 2.2. Since any element of R(j) is absolutely continuous with respect to R, by Girsanov's theory it admits a predictable intensity, see [START_REF] Jacod | Multivariate point processes: predictable representation, Radon-Nikodým derivatives, representation of martingales[END_REF]Thm. 4.5]. This will be used constantly in the rest of the article.

Reciprocal characteristics. We are going to give a characterization of the elements of R(j) in terms of reciprocal characteristics which we introduce right now.

Definitions 2.3 (Reciprocal characteristics of a Markov random walk). Let P ∈ P(Ω) be a Markov random walk with its jump intensity k which is assumed to satisfy (6) and to be continuously t-differentiable, i.e. for any

(z → z ) ∈ A → (P ) the function t → k(t, z → z ) is continuously differentiable on the semi-open time interval [0, 1). (a)
We define for all t ∈ [0, 1) and all (z → z ) ∈ A → (P ),

χ a [P ](t, z → z ) := ∂ t log k(t, z → z ) + k(t, z ) -k(t, z)
where k is defined at (5). (b) We define for all t ∈ [0, 1) and any closed walk c = (x 0 → • • • → x |c| = x 0 ) on the directed graph (X , A ↔ (P )) associated with the symmetric extension A ↔ (P ) of A → (P ),

χ c [P ](t, c) := (x i →x i+1 )∈A→(P ) k(t, x i → x i+1 ) (x i →x i+1 )∈A 0 (P ) k(t, x i+1 → x i )
where to emphasize the role of the reference intensity j. (e) A closed walk c as in item (b) above is shortly called a closed A ↔ (P )-walk.

A 0 (P ) := A ↔ (P ) \ A → (P ) = {(z → z ) ∈ A ↔ (P ) : k(t, z → z ) = 0, ∀t ∈ [0,
Note that no division by zero occurs and that under our regularity assumption on k, ∂ t acts on a differentiable function: χ [P ] is well defined.

The main results. They are stated at Theorems 2.4, 2.5 and Corollary 2.6. Theorem 2.4 gives a characterization of the reciprocal class of j in terms of the reciprocal characteristics. Theorem 2.5 provides an interpretation of the reciprocal characteristics of a reciprocal walk by means of short-time asymptotic expansions of some conditional probabilities. Putting together these theorems leads us to Corollary 2.6 which states a characterization of the reciprocal class in terms of these short-time asymptotic expansions.

Theorem 2.4 (Characterization of R(j)). We suppose that (X , →) satisfies Assumption 1.1 and j satisfies Assumption 1.5. A random walk P ∈ P(Ω) belongs to R(j) if and only if the following assertions hold for all x ∈ supp P 0 .

(i) The conditioned random walk P x is Markov3 , P x R x and its intensity k x is tdifferentiable on [0, 1).

(ii) The subgraph of all P x -active arcs doesn't depend on t and is given by

X (P x ) = X R (x, supp P x 1 ), A → (P x ) = A R → (x, supp P x 1 ). (iii) For any t ∈ [0, 1) and any (z → z ) ∈ A R → (x, supp P x 1 ), we have χ a [P x ](t, z → z ) = χ a [j](t, z → z ). (10)
(iv) For any t ∈ [0, 1) and any closed A R ↔ (x, supp P x 1 )-walk c, we have

χ c [P x ](t, c) = χ c [j](t, c). ( 11
)
About property (ii), notice that the dynamics of the reference random walk R plays an important role. Indeed, A R → (x, supp P x 1 ) is the subset of A → = A → (R) of the j-active arcs of all bridges of R from x to supp P x 1 . In some cases where the graph enjoys regularity, the property (iv) above can be weakened by only considering the identity (11) on a proper subset of the closed A R ↔ (x, supp P x 1 )walks. This is made precise below at Proposition 2.7.

The reciprocal characteristics come with a natural probabilistic interpretation which is expressed in terms of short-time asymptotics of the distribution of bridges. We shall show that they can be recovered as quantities related to Taylor expansions as h > 0 tends to zero of conditional probabilities of the form P (X [t,t+h] ∈ • | X t , X t+h ). This is the content of Theorem 2.5 below.

Let us introduce the notation needed for its statement. For any integer k ≥ 1 and any 0 ≤ t < 1, we denote by T t k the k-th instant of jump after time t. It is defined for k = 1 by T t 1 := inf {s ∈ (t, 1] : X s -= X s } and for any k ≥ 2 by T t k := inf s ∈ (T t k-1 , 1] : X s -= X s with the convention inf ∅ = +∞.

Theorem 2.5 (Interpretation of the characteristics). We suppose that (X , →) satisfies Assumption 1.1 and j satisfies Assumption 1.5. Let P be any random walk in R(j). (a) For any t ∈ [0, 1), any (z → z ) ∈ A → (P x ) and any measurable subset I ⊂ [0, 1] , we have

P (T t 1 ∈ t + hI | X t = z,X t+h = z , T t 2 > t + h) = I dr + h χ a [j](t, z → z ) I (1/2 -r) dr + o h→0 + (h). (12)
(b) For any t ∈ [0, 1) and any closed A → (P x )-walk c, we have

P (X t → X T t 1 → • • • → X T t |c| = X t ) = c, T t |c| < t + h < T t |c|+1 | X t = X t+h = χ c [j](t, c)h |c| /|c|! + o h→0 + (h |c| ).
(13) Note that in statement (b), only closed walks with respect to A → (P x ) and not its symmetrized version A ↔ (P x ) must be taken into account. This theorem is close to some results of [CDPR] where similar short time expansions are related to reciprocal characteristics of compound Poisson processes on R d .

In the same spirit that a Markov walk is specified by the Markov property and its jump intensity which can be obtained as the limit in small time of a conditional expectation, we obtain the following characterization of R(j).

Corollary 2.6 (Short-time expansions characterize R(j)). Let us suppose that in addition to Assumptions 1.1 and 1.5, the directed graph is symmetric, i.e.

A → = A ↔ ,
then a random walk P ∈ P(Ω) belongs to R(j) if and only if the following assertions hold for all x ∈ supp P 0 .

(i) The conditioned random walk P x is Markov, P x R x and its intensity k x is tdifferentiable on [0, 1). (ii) The subgraph of all P x -active arcs doesn't depend on t and is given by

X (P x ) = X R (x, supp P x 1 ), A → (P x ) = A R → (x, supp P x 1 ).
(iii) For any t ∈ (0, 1), any (z → z ) ∈ A → (P x ) and any measurable subset I ⊂ [0, 1] , the identity (12) is satisfied with P = P x . (iv) For any t ∈ (0, 1) and any closed A ↔ (P x )-walk c the identity (13) is satisfied with

P = P x .
The assumption A → = A ↔ is needed for Corollary 2.6 to hold. Without any restriction on the structure of the graph, this result is false in general. However, it is possible to relax this restriction in some specific situations. For instance, it is the case of the non-oriented triangle at page 24.

Proof. The necessary condition is a direct consequence of Theorems 2.4 and 2.5. For the sufficient condition, all we have to show is that the properties (a) and (b) of Theorem 2.5 respectively imply the properties (iii) and (iv) of Theorem 2.4. Based on identity (25), we see that the same calculations as in Theorem 2.5's proof at page 17 shows that replacing R x by P x and j by k x lead to the same conclusions with k x instead of j. It remains to compare the resulting expansions to conclude that (10) and (11) are satisfied.

It is possible to improve the statements of Theorem 2.4 and Corollary 2.6 as follows. We could replace item (i) in Theorem 2.4 and Corollary 2.6 by P is a reciprocal walk with a predictable intensity k X 0 .

Proofs of the main results

Let P be any element of R(j). We know with Proposition 2.1 that P R. Therefore P admits a predictable intensity k(t, X [0,t) ; z) and the related Girsanov formula (see [START_REF] Jacod | Multivariate point processes: predictable representation, Radon-Nikodým derivatives, representation of martingales[END_REF]) is for each x ∈ supp P 0 ,

dP x dR x = 1 {τ =∞} exp 0<t≤1:X t -=Xt log k j (t,X [0,t) ; X t ) - [0,1] z:X t -→z (k -j)(t, X [0,t) ; z) dt ( 14
)
where the stopping time τ is given by

τ := inf t ∈ [0, 1); k(t, X [0,t) ; X t ) = 0 or [0,t] z:X s -→z k(s, X [0,s) ; z) ds = ∞ ∈ [0, 1] ∪ {∞} with the convention inf ∅ = ∞.
Note that R x -almost surely j(t, X [0,t) ; X t ) = j(t, X t -→ X t ) > 0, for all t ∈ [0, 1) and

[0,1) j(t, X t -) dt < ∞.
As a general result [START_REF] Léonard | Reciprocal processes. A measure-theoretical point of view[END_REF], it is known that for any reciprocal walk P and any x ∈ supp P 0 , P x is Markov. Therefore, we already know that the intensity k has the Markov form k(t, X [0,t) ; z) = k(t, X t -→ z). We will recover this result without invoking this general result.

Lemma 3.1 (HJB equation). For any x ∈ X and any nonnegative function

h 1 : X → [0, ∞) such that E R x h 1 (X 1 ) = 1, the function ψ x defined by ψ x (t, z) := log E R x [h 1 (X 1 )|X t = z] ∈ R, t ∈ (0, 1), z ∈ X R (x, supp h 1 ) ψ x (0, x) := 0, t = 0, z = x,
is a well-defined real function which satisfies the following regularity properties: (i) for all z ∈ X R (x, supp h 1 ), t → ψ x t (z) s continuously differentiable on (0, 1), (ii) lim t→0 + ψ x t (x) =: ψ x 0 (x) = 0, (iii) lim t→1 -ψ x t (z) =: ψ x 1 (z) ∈ R exists for all z ∈ supp h 1 , and for each 0 ≤ T ≤ 1, the Itô formula

ψ x T (X T ) := log h T (X T ) = 0<t≤T ;X t -=Xt [ψ x t (X t ) -ψ x t (X t -)] + [0,T ] ∂ t ψ x t (X t ) dt ∈ R, h 1 (X 1 )R x -a.s. (15)
is meaningful. Furthermore, ψ x is a classical solution of the Hamilton-Jacobi-Bellman equation

       ∂ t ψ t (z) + z :(z→z )∈A R → (x,supp h 1 ) j(t, z → z ) [e ψt(z )-ψt(z) -1] = 0, t ∈ (0, 1), z ∈ X R (x, supp h 1 ) lim s→1 -ψ s (y) = log h 1 (y), t = 1, y ∈ supp h 1 . (16)
It is important to see that the identity (15) is only valid almost surely with respect to 1 supp h 1 (X 1 ) R, but not with respect to R.

Proof. The function h(t, z)

:= E R x [h 1 (X 1 ) | X t = z], 0 < t ≤ 1, z ∈ X (R x
) is space-time harmonic. This means that it satisfies the Kolmogorov equation

(∂ t + L t )h(t, z) = 0, 0 < t < 1, z ∈ X (R x ).
Remark that it is needed that z ∈ supp R x t for the conditional expectation to be well defined as a finite number. But the assumption (7) implies that supp R x t = X (R x ) for all 0 < t ≤ 1. We obtain h(t, •) = ←exp( 1 t L s ds) (h 1 ) where the ordered exponential is defined by ←exp

1 t L s ds := Id + n≥1 t≤s 1 ≤•••≤sn≤1 L s 1 • • • L sn ds 1 • • • ds n
and the continuity of L t (recall that j is t-continuous) ensures that its formal left tderivative is -L t ←exp 1 t L s ds . Furthermore, ←exp 1 t L s ds and L t ←exp 1 t L s ds are absolutely summable series under the assumption (9). More precisely, for any nonnegative h 1 in L 1 (R x 1 ), we know by a martingale argument that h t = ←exp

1 t L s ds h 1 is in L 1 (R x t )
. Hence, h(•, z) is continuous at t = 1 for all z ∈ X (R x ) and h(•, x) is continuous at t = 0. In addition, with the assumed uniform boundedness of L t , we see that L t ←exp

1 t L s ds h 1 = L t h t is also in L 1 (R x t )
. Therefore, h is continuously left t-differentiable on [0, 1). But the continuity of the left derivative implies both the existence and the continuity of the derivative. Consequently, the backward differential system

(∂ t + L t )h(t, z) = 0, 0 < t < 1, z ∈ X (R x ), lim t→1 -h(t, y) =: h(1, y) = h 1 (y), t = 1, y ∈ X (R x ), (17)
can be considered in the classical sense and

lim t→0 + h(t, x) =: h(0, x) = 1 since h(0, x) = 1 is fixed by hypothesis.
On the other hand, the assumption (7) implies that for all 0 < t < 1 and z ∈ X R (x, supp h 1 ) ⊂ X (R x ), h(t, z) is positive. It follows that we are allowed to define ψ x t (z) := log h(t, z) as a real number for any 0 < t < 1 and any z ∈ X R (x, supp h 1 ). Of course, for t = 0 one must only consider z = x and lim t→0 + ψ x t (x) = ψ x 0 (x) = 0. We have shown that the regularity properties (i,ii,iii) are satisfied. The Itô formula

ψ x T (X T ) = ψ x S (X S ) + S<t≤T ;X t -=Xt [ψ x t (X t ) -ψ x t (X t -)] + [S,T ] ∂ t ψ x t (X t ) dt ∈ (-∞, ∞), h 1 (X 1 ) R x -a.s. ( 18
)
is meaningful for all 0 < S ≤ T < 1. Indeed, under Assumption 1.5(1) there are finitely many jumps R x -a.s. and we have already seen that ψ x t (X t ) is finite for every

0 ≤ t < 1, h 1 (X 1 ) R x -a.s. Therefore, ψ x T (X T ), ψ x S (X S ) and S<t≤T ;X t -=Xt [ψ x t (X t ) -ψ x t (X t -)] are finite. It follows that the integral (S,T ] ∂ t ψ x t (X t
) dt is also well-defined h 1 (X 1 ) R x -a.s. Letting S tend to 0 and T to 1 in (18), with the limits (ii) and (iii) we obtain (15) where the integral [0,T ) ∂ t ψ x t (X t ) dt is well defined h 1 (X 1 ) R x -a.s. Finally, considering h = e ψ x in (17) gives the HJB equation ( 16) and completes the proof of the lemma.

The following result is the key lemma of the proof of Theorem 2.4. Lemma 3.2. If the random walk P ∈ P(Ω) belongs to R(j) then P R and for all x ∈ supp P 0 , the following assertions are satisfied.

(i) The conditioned random walk P x is Markov, P x R x and its intensity k x is tdifferentiable on [0, 1). (ii) The subgraph of all P x -active arcs doesn't depend on t and is given by

X (P x ) = X R (x, supp P x 1 ), A → (P x ) = A R → (x, supp P x 1
). (iii) There exists a real function ψ x : (0, 1) × X R (x, supp P x 1 ) → R such that for all z ∈ X R (x, supp P x 1 ), t → ψ x t (z) s continuously differentiable on (0, 1) and k x and ψ x are linked by the relations

log k x j (t, z → z ) = ψ x t (z ) -ψ x t (z), (19)
∂ t ψ x t (z) + ( kx -j)(t, z) = 0, (20)
for all t ∈ (0, 1), z ∈ X R (x, supp P x 1 ) and (z → z ) ∈ A R → (x, supp P x 1 ). In (20), the average frequency of jumps kx (t, z) := z :z→z k x (t, z → z ) is finite everywhere on [0, 1) × X R (x, supp P x 1 ). Furthermore, one can choose ψ x in (iii) such that it solves the HJB equation (16) with h x 1 = dP x 1 /dR x 1 . Recall that P x R x implies that P x admits a jump intensity k x .

Proof. Let us first take some P ∈ R(j) and show that it satisfies the announced properties.

As supp P 01 ⊂ supp R 01 , we can apply Proposition A.1 which states that for every x ∈ supp P 0 , we have

P x R x , P x = h x (X 1 ) R x and E R x h x (X 1 ) = 1 where h x := dP x 1 /dR x 1 .
Comparing with (14), we see that the events {τ = ∞} and {X 1 ∈ supp h x = supp P x 1 } match, up to an R x -negligible set. This proves that A → (t, P x ) doesn't depend on t and that it is equal to A R → (x, supp P x 1 ). Let us define

ψ x t (z) := log E R x (h x (X 1 ) | X t = z
). We know that ψ x shares the regularity properties (i), (ii) & (iii) of Lemma 3.1. Applying (15) with T = 1 to P x = h x (X 1 ) R x leads us to

dP x dR x = 1 {X1∈supp P x 1 } exp 0<t≤1;X t -=Xt [ψ x t (X t ) -ψ x t (X t -)] + (0,1] ∂ t ψ x t (X t ) dt .
Comparing with (14), we obtain

0<t≤1;X t -=Xt log k j (t, X [0,t) ; X t ) - [0,1] dt z:X t -→z (k -j)(t, X [0,t) ; z) = 0<t≤1;X t -=Xt [ψ x t (X t ) -ψ x t (X t -)] + (0,1] ∂ t ψ x t (X t ) dt, 1 {X1∈supp P x 1 } R x -a.s.
Identifying the jumps, we see that

1 {X t -=Xt} log k j (t, X [0,t) ; X t ) = ψ x t (X t ) -ψ x t (X t -), 1 {X1∈supp P x 1 } R x -a.s. (21)
Hence, for any z ∈ X R (x, supp P x 1 ) and (z → z ) ∈ A R → (x, supp P x 1 ), we can write

1 {X t -=z} k(t, X [0,t) ; z ) = k x (t, z → z ), 1 {X1∈supp P x 1 } R x -a.
s. signifying that k(t, X [0,t) ; •) only depends on (t, X t -). This shows that P x is Markov. More precisely, (21) gives us (19). By Lemma 3.1 we know that ψ x satisfies the HJB equation ( 16). With (19), this leads us to (20). Remark that (19) also implies that k x is t-continuously differentiable on [0, 1). Note that since j is finite everywhere, it follows with (20) that k is also finite everywhere. This completes the proof of the lemma.

Proof of Theorem 2.4. In order to simplify notation, for a given x ∈ supp P 0 , we write Z → = A R → (x, supp P x 1 ) and Z ↔ = A R ↔ (x, supp P x 1 ) during this proof. • Proof of the necessary condition. Let us show that P ∈ R(j) shares the announced properties. The first items (i) and (ii) are already proved at Lemma 3.2. Now, we rely on Lemma 3.2(3). Differentiating (19) and plugging (20) into the resulting identity gives us χ a [k x ] = χ a [j] on Z → which is (iii). Let us prove (iv). For any t ∈ (0, 1) and any

(z → z ) ∈ Z → , we denote (t, z → z ) = log k x j (t, z → z ). If the reversed arc (z → z) is also in Z → , we see with (19) that (t, z → z) = -(t, z → z ).
Otherwise, we extend (t, •) from Z → to Z ↔ by means of this identity. Therefore, t,c) for all closed Z ↔ -walks, which is the desired result.

(t, z → z ) = ψ x t (z ) -ψ x t (z), ∀(z → z ) ∈ Z ↔ and we are allowed to apply Lemma B.2 to obtain χ c [k x ](t, c) = χ c [j](
• Proof of the sufficient condition. Take P ∈ P(Ω) such that for every x ∈ supp P 0 , P x is Markov and its intensity k x satisfies the properties (i-iv) of Theorem 2.4. Fix x ∈ supp P 0 . We start exploiting the property (iv). Because χ c [k x ](t, c) = χ c [j](t, c) for any t ∈ (0, 1) and any closed Z ↔ -walk c, by Lemma B.2 there exists a function ϕ x which satisfies

ϕ x (t, z ) -ϕ x (t, z) = log k x j (t, z → z ), ∀t ∈ (0, 1), (z → z ) ∈ Z → . (22)
On the other hand, the property (iii) implies that ∂ t ϕ x (t, z) + ( kxj)(t, z) = ∂ t ϕ x (t, z ) + ( kxj)(t, z ) for all t ∈ (0, 1) and (z → z ) ∈ Z → . Since ϕ x is defined up to some timedependent additive function, we can decide that ∂ t ϕ x (t, x) + ( kxj)(t, x) = 0, for all t ∈ (0, 1). Therefore, we obtain with the property (ii) and our assumption (10) that

∂ t ϕ x (t, z) + ( kx -j)(t, z) = 0, ∀t ∈ (0, 1), z ∈ X R (x, supp P x 1 ). (23)
We know with the property (i) that P x R x . Restricting the path measures to the subσ-field σ(X [0,t] ) for any 0 ≤ t < 1, and plugging ( 22) and (23) into Girsanov's formula (14), we obtain

dP x [0,t] dR x [0,t] = 1 {τt=∞} exp 0<s≤t:Xs =X s - [ϕ x (s, X s ) -ϕ x (s, X s -)] + (0,t) ∂ s ϕ x (s, X s ) ds where τ t := inf r ∈ [0, t); k x (r, X r -→ X r ) = 0 or (0,r] ∂ s ϕ x (s, X s ) ds = -∞ ∈ [0, t] ∪ {∞} .
Thanks to property (ii), k x does not vanish on [0, 1) × Z → . Hence, τ t is finite if and only if [0,r] ∂ s ϕ x (s, X s ) ds = -∞ for some 0 < r ≤ t. But for any 0 ≤ t < 1, we have

0<s≤t:Xs =X s - [ϕ x (s, X s ) -ϕ x (s, X s -)] + (0,t] ∂ s ϕ x (s, X s ) ds = ϕ x (t, X t ) -ϕ x (0, X 0 ).
This implies that (0,t] ∂ s ϕ x (s, X s ) ds is finite for every 0 ≤ t < 1 and it follows that τ t is infinite R x -a.s. for all 0 ≤ t < 1. Consequently,

dP x [0,t] dR x [0,t] = exp(ϕ x (t, X t ) -ϕ x (0, x)) (24)
since the prefactor 1 {τt=∞} does not vanish. Let us denote Z := dP x dR x and Z

t := E R x (Z | X [0,t] ) = dP x [0,t] dR x [0,t]
for all 0 ≤ t < 1. We see with (24) that Z t is X t -measurable. This implies that Z is X [t,1] -measurable for all 0 ≤ t < 1 and consequently that Z is X 1 -measurable. We conclude with Proposition A.1 that P belongs to R(j).

Proof of Theorem 2.5. Let us fix x ∈ supp P 0 and t ∈ (0, 1). Note that for h > 0 such that t + h < 1 and (z → z ) ∈ A R → (x, supp P x 1 ), the conditional distribution P (• | X t = z, X t+h = z ) is well defined. Because of (43) and the reciprocal property of P , we have

P (T t 1 ∈ t + hI | X t = z, X t+h = z , T t 2 > t + h) = R(T t 1 ∈ t + hI | X t = z, X t+h = z , T t 2 > t + h). ( 25
)
Therefore it suffices to do the proof with R instead of P .

• Proof of (a). Recall that for a Poisson process with intensity λ(t) the density of the law of the first instant of jump is t → λ(t) exp(-

t 0 λ(s) ds), t ≥ 0. Therefore, R(T t 1 ∈ t + hI, X t+h = z , T t 2 > t + h | X t = z) = hI j(t + r, z) exp - r 0 j(t + s, z) ds j(t + r, z → z ) j(t + r, z) exp - h r j(t + s, z ) ds dr = h I exp - hr 0 j(t + s, z) ds j(t + hr, z → z ) exp - h hr j(t + s, z ) ds dr.
Using the following expansions as h tends to zero:

exp - hr 0 j(t + s, z) ds = 1 -j(t, z)hr + o(h), exp - h hr j(t + s, z ) ds = 1 -j(t, z )(1 -r)h + o(h), j(t + hr, z → z ) = j(t, z → z ) + ∂ t j(t, z → z )hr + o(h),
we obtain

R(T t 1 ∈t + hI, X t+h = z , T t 2 > t + h | X t = z) = hj(t, z → z ) I 1 + h ∂ t j(t, z → z ) j(t, z → z ) r -j(t, z)r -j(t, z )(1 -r) dr + o(h 2 ) = hj(t, z → z ) I 1 + h χ a [j](t, z → z )r -j(t, z ) dr + o(h 2 ).
In particular, with I = [0, 1] this implies that

R(X t+h = z , T t 2 > t + h | X t = z) = hj(t, z → z ) 1 + h χ a [j](t, z → z )/2 -j(t, z ) + o(h 2 ).
Taking the ratio of these probabilities leads us to

R(T t 1 ∈ t + hI | X t = z,X t+h = z , T t 2 > t + h) = I 1 + h χ a [j](t, z → z )r -j(t, z ) + o(h) 1 + h χ a [j](t, z → z )/2 -j(t, z ) + o(h) dr = I 1 + h{ χ a [j](t, z → z )(r -1/2)} dr + o(h).
With (25) this gives (12).

• Proof of (b). Since R(X t = X t+h = z) = R(X t = z)(1 + o(1)) as h → 0 + , we can write the proof with R(• | X t = z) instead of R(• | X t = X t+h = z). Therefore, if c = (z = x 0 → x 1 • • • → x |c| = z), R (X t → X T t 1 → • • • → X T t |c| ) = c, T t |c| < t + h < T t |c|+1 | X t = z = {t<t 1 <•••<t |c| <t+h} |c| i=1 exp - t i t i-1 j(s, x i ) ds j(t i , x i → x i+1 ) × exp - t+h t |c| j(s, z) ds dt 1 • • • dt |c| = χ c [j](t, c)(1 + o(1)) {t<t 1 <•••<t |c| <t+h} exp - c i=1 t i+1 t i j(s, x i ) ds - t+h t |c| j(s, z) ds dt 1 • • • dt |c| = χ c [j](t, c)h |c| /|c|! + o(h |c| )
where we used the convention that t 0 := t. This completes the proof of the theorem.

More results

We give some additional results about the characterization of the reciprocal class R(j).

Jump intensity. Proposition 4.1 below expresses characterizations of the reciprocal class in terms of the jump intensities by exploiting the fact that for any P ∈ R(j) and each x, P x is an h-transform of R x .

Proposition 4.1 (Representation of the intensity of an element of R(j)). Let P ∈ P(Ω) be a random walk. The following assertions are equivalent. (a) P ∈ R(j).

(b) There exists h : X 2 → [0, ∞) such that

P x = h(x, X 1 ) R x with y∈X R x 1 (y)h(x, y) = 1, for all x ∈ supp P 0 . (c) There exists g : X 2 → [0, ∞) such that (i) supp P 0 = {g(x, y o ) > 0 for some y o }, (ii
) for all x ∈ supp P 0 , y∈X R x 1 (y)g(x, y) < ∞ and (iii) P is a random walk with intensity

k(t, X [0,t) , X t -→ z) = 1 {X t -∈X R (x,supp g(x,•))} g X 0 t (z) g X 0 t (X t -) j(t, X t -→ z), R-a.s. ( 26
)
where for any 0 ≤ t ≤ 1 and z ∈ X (R x ),

g x t (z) := E R [g(x, X 1 ) | X t = z] = y∈X r(t, z; 1, y)g(x, y),
with r(t, z; 1, y) := R(X 1 = y | X t = z). In addition, for each x ∈ supp P 0 , g x solves the heat equation

(∂ t + L t )g x = 0, 0 ≤ t < 1, g x 1 = g(x, •), t = 1. ( 27
)
The link between h and g is h(x, y) = g(x, y)/g x 0 (x) where g x 0 (x) = y∈X R x 1 (y)g(x, y) is finite.

Proof. The equivalence of (a) and (b) is proved at Proposition A.1. Let us prove the equivalence of (b) and (c). Statement (b) tells us that P x is an h-transform of R x . It is a general result that the extended generator of this h-transform is given for any function u with a finite support by

A x t u(X t -) = L t u(X t -) + Γ t (g x t , u)(X t -)/g x t (X t -), P x -a.s. where Γ t (g t , u)(z) := z :z→z j(t; z → z )[g x t (z ) -g x t (z)][u(z ) -u(z)]
is the carré du champ operator. This identity characterizes the h-transformation. Note that it is only valid P x -almost surely and not R x -almost surely. As for any t ∈ [0, 1) and z ∈ X (R x ),

g x t (z) > 0 ⇔ z ∈ X R (x, supp g(x, •)), we see that A x t u(z) = 1 {z∈X R (x,supp g(x,•)} z :z→z j(t; z → z )g x t (z )/g x t (z)[u(z ) -u(z)
] which gives (26). This completes the proof Proposition 4.1.

A direct proof of the equivalence of (b) and (c), which does not rely on a general result about the extended generator of an h-transform, consists of identifying dP x /dR x = h(x, X 1 ) by means of Girsanov's formula ( 14) and to apply the representation result (27) under its HJB form (16), via the transformation g = e ψ , as in the proof of Lemma 3.2.

As a special case of Proposition 4.1, we recover the known fact that for each (x, y) ∈ supp R 01, the jump intensity k xy of the bridge R xy is

k xy (t, z → z ) = r(t, z ; 1, y) r(t, z; 1, y) j(t, z → z ), 0 ≤ t < 1, (z → z ) ∈ A R → (x, {y}). ( 28
)
Characteristic equation. We see with Theorem 2.4 that for any given Markov intensity j, the description of the reciprocal class R(j) is linked to the solution of some equation of the form

A → (k x ) = A R → (x, Y x ), χ [k x ] = χ [j],
x ∈ S (29)

where we use notation

χ [P x ] =: χ [k x ]
to emphasize the role of the intensity. In (29), the given subsets S ⊂ X and

Y x ⊂ X (R x ), x ∈ S
are non-empty and the unknown is the collection of Markov intensities (k x ; x ∈ S). More precisely, (29) is a shorthand for the following list of properties that must hold for all x ∈ S.

(i) The intensity k x is t-differentiable on [0, 1).

(ii) The subgraph of all k x -active arcs doesn't depend on t and is

A → (k x ) := {(z → z ) : k x (t, z → z ) > 0} = A R → (x, Y x ). (iii) For any t ∈ [0, 1) and any (z → z ) ∈ A R → (x, Y x ), we have χ a [k x ](t, z → z ) = χ a [j](t, z → z ).
(iv) For any t ∈ [0, 1) and any closed A R ↔ (x, Y x )-walk c, we have

χ c [k x ](t, c) = χ c [j](t, c).
Because of Theorem 2.4, we say that (29) is a characteristic equation. It is natural to ask for the solutions (k x ; x ∈ S) of (29) where j, S and (Y x , x ∈ S) are given. (a) Take any nonnegative function g :

X 2 → [0, ∞) such that supp g ⊂ supp R 01 and y∈X R x 1 (y)g(x, y) < ∞ for all x ∈ X . Let us denote g x t (z) := E R [g(x, X 1 ) | X t = z] > 0, for any t ∈ [0, 1) and z ∈ X R (x, supp g(x, •)). Then, k x (t, z → z ) := g x t (z ) g x t (z) j(t, z → z ), t ∈ [0, 1), (z → z ) ∈ A R → (x, supp g(x, •))) (30)
solves (29) with S := {x ∈ X ; g(x, y) > 0 for some y ∈ X } and Y x = supp g(x, •). (b) Conversely, any solution (k x ; x ∈ S) of (29) which verifies the additional requirement ∀x ∈ S, ∀0 ≤ t < 1, sup

y∈Y x t 0 kx (s, y) ds < ∞, (31)
has the above form (30) for some function g and for any x ∈ S,

P x := g(x, X 1 ) g x 0 (x) R x ∈ P(Ω),
defines a Markov probability measure on Ω with intensity k x given by (30).

The main point about this result is that unlike Theorem 2.4 and Proposition 4.1, it is not assumed that k x given at (30) is the intensity of a random walk. It might happen a priori that such a random process "explodes" in finite time with a positive probability.

The assumption (31) rules this bad behavior out.

Proof. The proof mainly consists of addressing some comments about the proof of Theorem 2.4. The first statement (a) follows from a straightforward computation. The regularity issues are direct consequences of Lemma 3.1. Statement (b) is proved by considering the proof of the sufficient condition of Theorem 2.4 at page 16. Let k x be a solution of (29). Mimicking the Girsanov formula (14), let us define

Q x := Z x 1 R x with Z x t := 1 {τ >t} exp 0<s<t:X s -=Xs log k x j (s, X s -→ X s )- t 0 ( kx -j)(s, X s ; y) dt , 0 ≤ t ≤ 1
and the stopping time τ defined by

τ := inf s ≤ 1; k x (s, X s -→ X s ) = 0 or s 0 kx (r, X r ) dr = ∞ ∈ [0, 1] ∪ {∞} .
Let us show that under the assumption (31), Q x is a probability measure. The process Z x is a nonnegative local R x -martingale. As such it is also an R x -supermartingale. In particular,

Q x (Ω) = E R x Z x 1 ≤ 1, but it might happen that Q x (Ω) < 1, in which case Q x is
not a probability measure. However, the property (ii) implies that k x (t, X t -→ X t ) > 0, ∀0 ≤ t < 1, R x -a.s. and the assumption (31) implies that for all 0 ≤ t < 1, τ > t, R x -a.s. and (Z x s ) 0≤s≤t is an R x -martingale. In particular, E R x Z x t = 1 and Q x [0,t] is probability measure for all 0 ≤ t < 1, which in turns implies that Q x is a probability measure, since without loss of generality, one can modify the path space Ω by throwing away the R-negligible event of all paths that jump at t = 1.

Following almost verbatim the proof of the sufficient condition of Theorem 2.4, we show that there exists a function ϕ x such that, as in (24), Z x t = exp(ϕ x (t, X t )ϕ x (0, x)), 0 ≤ t < 1. It follows from the above modification of Ω at time 1 that t → Z x t admits a version which is left-continuous at 1 and

Q x = exp(ϕ x 1 (X 1 ) -ϕ x (0, x)) R x , where the limit ϕ x 1 (X 1 ) := lim t→1 -ϕ x (t, X t ) ∈ [-∞, ∞) exists R x -
almost surely. Now, we are back to Proposition 4.1 with the functions h(x, y) = exp(ϕ x 1 (y)ϕ x (0, x)) and g(x, y) = exp(ϕ x 1 (y)) where as a convention exp(-∞) = 0.

Examples

In this series of examples, we illustrate Theorem 2.4 improved by Proposition 2.7. We compute the reciprocal characteristic χ [j] and sometimes we consider the characteristic equation (29).

Directed tree. Let R be the simple random walk on a directed tree (X , A → ). By "directed tree", it is meant that

(z → z ) ∈ A → implies that (z → z) ∈ A → , while "simple" means that j(t, z → z ) = 1 for all (z → z ) ∈ A → , 0 ≤ t < 1.
The closed walks of the corresponding undirected tree A ↔ are clearly generated by the set E of all edges, i.e. closed walks of length two, which matches with A ↔ . Therefore, the closed walk characteristic is trivial: χ c [k](t, z ↔ z ) = 1 for all 0 ≤ t < 1, (z ↔ z ) ∈ A ↔ and any intensity k such that A → (k) = A → . In this situation, only the arc component

χ a [j](t, z → z ) = deg(z ) -deg(z), 0 ≤ t < 1, (z → z ) ∈ A → ,
is relevant, where deg(z) := # {z ∈ X : (z → z ) ∈ A → } is the outer degree, i.e. the number of offsprings of z. The characteristic equation is

∂ t log k x (t, z → z ) + kx (t, z ) -kx (t, z) = out(z ) -out(z), 0 ≤ t < 1, (z → z ) ∈ A R → (x, Y), for some Y ⊂ X (R x ).
Intensity of a bridge. In particular, the intensity j xy of any bridge R xy satisfies A → [j xy ] = w xy : the only walk leading from x to y, and

∂ t log j xy (t, z → z )+1 {z =y} j xy (t, z → z ) -j xy (t, z → z ) = 1 {z =y} out(z ) -out(z), 0 ≤ t < 1, (z → z ) ∈ w xy ,
where z → z → z are consecutive vertices.

Birth and death process. The vertex set is X = N with the usual graph structure which turns it into an undirected tree. The reference walk R is governed by the timehomogeneous Markov intensity j(z → (z +1)) = λ > 0, z ≥ 0 and j(z → (z -1)) = µ > 0, z ≥ 1. Clearly, the of edges E = {(z ↔ z + 1), z ∈ N} generates C and the characteristics of the reference intensity are:

   χ a [j](z → z + 1) = χ a [j](z + 1 → z) = 0, z ≥ 1, χ a [j](0 → 1) = -χ a (1 → 0) = µ, χ c [j](z ↔ z + 1) = λµ, z ≥ 0.
Time-homogeneous Markov walks in R[j]. Let us search for such a random walk P ∈ P(Ω). We denote λ(z) the intensity of (z → z + 1) and μ(z + 1) the intensity (z + 1 → z) of the Markov walk P . By Theorem 2.4, P ∈ R[j] if and only if

   λ(z + 1) + μ(z + 1) -λ(z) -μ(z) = 0, z ≥ 1 λ(1) + μ(1) -λ(0) = µ, λ(z)μ(z + 1) = λµ, z ≥ 0.
The solutions to the the above set of equations can be parametrized by choosing λ(0) arbitrarily and finding λ(z + 1), μ(z + 1) recursively as follows

μ(z + 1) = λ(z) -1 λµ, z ≥ 0, λ(z + 1) = µ + λ(0) -μ(z + 1), z ≥ 1.
With some simple computations one can see that for any large enough λ(0), the above system admits a unique positive and bounded solution. Hence, the corresponding Markov walk has its sample paths in Ω and it is in R[j].

Hypercube. Let X = {0, 1} d be the d-dimensional hypercube with its usual directed graph structure and let {g i } d i=1 be the canonical basis. For x ∈ X , we set x i := x + g i and x ik = x + g i + g k where we consider the addition modulo 2. Let

S := (x → x i → x ik → x k → x), x ∈ X , 1 ≤ i, k ≤ d
be the set of all directed squares. The subset

S ∪ E (32)
generates the closed walks. One can produce a smaller generator for the closed walks by imposing i < k in the definition of S. However, no more than this can be done since E does not generate C there are no closed walks of length 3.

The bridge of a simple random walk on the discrete hypercube. Let j be the simple random walk on the hypercube. The intensity j xy (t, z → z ) of the xy-bridge can be computed explicitly with (28) since the transition density of the random walk is known explicitly. We have

j xy (t, z → z i ) = cosh(1 -t)/ sinh(1 -t), if z i = y i , sinh(1 -t)/ cosh(1 -t), if z i = y i , (33)
where z i and y i ∈ {0, 1} are the i-th coordinates of z and y ∈ X .

We provide an alternate proof based on the characteristic equation ( 29). First, it is immediate to see that under any bridge, all arcs of the hypercube are active at any time.

From χ c [j xy ] = χ c [j], we deduce that the arc function log(j/j xy )(t, •) is the gradient of some potential ψ t , see Lemma B.2. The equality of the arc characteristics implies that for all t ∈ (0, 1) and z ∈ X

∂ t ψ(t, z) + d i=1 [exp(ψ t (z i ) -ψ t (z)) -1] = ∂ t ψ(t, x) + d i=1 [exp(ψ t (x i ) -ψ t (x)) -1].
Since ψ is defined up the addition of a function of time, we can assume without loss of generality that for all 0 < t < 1, ∂ t ψ t (x) + d i=1 [exp(ψ t (x i )ψ t (x)) -1] = 0. Hence ψ solves the HJB equation

∂ t ψ(t, z) + d i=1 [exp(ψ t (z i ) -ψ t (z)) -1] = 0, t ∈ [0, 1), z ∈ X . ( 34
)
Going along the lines of the proof of Theorem 2.4, in particular equation ( 24), allows to deduce that the boundary data for ψ are

lim t→1 ψ t (z) = -∞, if z = y, 0, if z = y. (35)
One can check with a direct computation that the solution (34) & ( 35) is

ψ(t, z) = d i=1 log[1 + (-1) (z i -y i ) e 2(1-t) ] (36)
where the subtraction is considered modulo two. By the definition of ψ, we have

j xy (t, z → z i ) = j(t, z → z i ) exp(ψ t (z i ) -ψ t (z)) = exp(ψ t (z i ) -ψ t (z))
and ( 33) follows with a simple computation.

Two triangles. We look at two simple directed trees based on triangles. The reference intensity is j ∆ on each arc and we want to find the intensity of the AB-bridge: j AB (t, •), using the characteristic equation. Imposing the equality of the closed walk characteristics implies that log(j AB /j)(t, •) is the gradient of some potential ψ t : X → R. The equality of the arc characteristics implies that ψ solves the HJB equation

             ∂ t ψ t (A) + j ∆ [exp(ψ t (B) -ψ t (A)) -1] = 0, ∂ t ψ t (B) + j ∆ [exp(ψ t (C) -ψ t (B)) -1] = 0, ∂ t ψ t (C) + j ∆ [exp(ψ t (A) -ψ t (C)) -1] = 0, lim t→1 ψ t (A) = lim t→1 ψ t (C) = -∞, lim t→1 ψ t (B) = 0, (37)
where the boundary conditions for ψ follow from (24). Since the HJB equation is the logarithm of the Kolmogorov backward equation, we obtain the following solutions

     ψ t (A) = log{ 1 3 + 2 3 exp(-3 2 j ∆ (1 -t)) sin[ √ 3 2 j ∆ (1 -t) -π 6 ]}, ψ t (B) = log{ 1 3 + 2 3 exp(-3 2 j ∆ (1 -t)) cos[ √ 3 2 j ∆ (1 -t)]}, ψ t (C) = log{ 1 3 -2 3 exp(-3 2 j ∆ (1 -t)) sin[ √ 3 2 j ∆ (1 -t) + π 6 ]}. ( 38
)
We deduce the following identities

                             j AB T (t, A → B) = j ∆ exp 3 2 j ∆ (1 -t) + 2 cos √ 3 2 j ∆ (1 -t) exp 3 2 j ∆ (1 -t) + 2 sin √ 3 2 j ∆ (1 -t) -π 6 , j AB T (t, B → C) = j ∆ exp 3 2 j ∆ (1 -t) -2 sin √ 3 2 j ∆ (1 -t) + π 6 exp 3 2 j ∆ (1 -t) + 2 cos √ 3 2 j ∆ (1 -t) , j AB T (t, C → A) = j ∆ exp 3 2 j ∆ (1 -t) + 2 sin √ 3 2 j ∆ (1 -t) -π 6 exp 3 2 j ∆ (1 -t) -sin √ 3 2 j ∆ (1 -t) + π 6 . (39)
Non-oriented triangle. The triangle X = {A, B, C} is now equipped with the directed graph structure A = {(A → B), (B → C), (A → C)} where we reverted the direction of the arc on the edge AC, as shown at Figure 1. The characteristic associated to the closed walk

(A → B → C → A) is j(A → B)j(B → C)/j(C → A).
Since it is not a closed walk of the graph (X , A ), the interpretation given at Theorem 2.5 is not available for this characteristic. However, we can reason in a similar way to obtain a probabilistic interpretation of this characteristic as well. Let R A be the reference walk conditioned to start from A. If the walk reaches C at time h it is easy to see that as h → 0, this has happened essentially only by using directly the arc (A → C). Therefore, we obtain

R A (X h = C) = j(A → C)h + o(h).
Similarly, the probability of going from A to C using the path

(A → B → C) is R A (X 0 → X T 1 → X T 2 ) = (A → B → C), T 2 ≤ h, T 3 > h = j(A → B)j(B → C)h 2 /2 + o(h 2 ). Consequently, R A (X 0 → X T 1 → X T 2 ) = (A → B → C), T 2 ≤ h, T 3 > h | X h = C) = j(A → B)j(B → C) 2j(A → C) h + o(h).
We see that the characteristic is twice the driving factor of the expansion of this probability as h tends to zero. Note that while the characteristic the oriented triangle is associated to a probability of order h 3 , in the present case it is associated to a probability of order h. Planar graphs. Let (X , ↔) be an undirected planar graph. We fix a planar representation and consider the set F of all counter-clockwise closed walks along the faces. We denote by E the set of all edges seen as closed 2-walks. Then,

F ∪ E (40)
generates the closed walks of the planar graph.

Triangular prism. The set X = {A 0 , B 0 , C 0 , A 1 , B 1 , C 1 } is endowed with the directed graph structure as in Figure 2 where one should see the left triangle A 0 B 0 C 0 on the picture as the bottom face of the prism and the horizontal arcs of the picture as flowing along the three vertical edges of the prism. The intensity j is time-homogeneous and j(z → z ) = j ∆ if (z → z ) belongs to a triangular face with one given orientation and j(z → z ) = j v if (z → z ) connects the triangular faces. The closed walk characteristics

j Δ j v j Δ j v j Δ j v j v j Δ j v j Δ j v j Δ A 0 B 0 C 0 A 1 B 1 C 1 Figure 2. Triangular prism.
of the triangular faces is χ ∆ = j 3 ∆ and for the closed walks of length two corresponding to the vertical edges we have χ v = j 2 v . We are going to derive an explicit expression of the jump intensity j A 0 B 1 of the bridge from A 0 to B 1 , see (41) below. The nice feature of this example is that it is a non trivial planar graph where the intensity of the bridge can be explicitly computed. This is achieved by putting together some already done calculations about the hypercube and the oriented triangle. Without getting into details, the fact that the prism is the product of the oriented triangle treated at page 23 and the complete graph with two vertices, which is the discrete hypercube of dimension 1, is the key of the following computation. As in the previous example, imposing the characteristic equation leads to the fact that j A 0 ,B 1 (t, •)/j(•) is the gradient of some potential ψ which solves the following HJB equation:

                   ∂ t ψ t (A 0 ) + j ∆ [exp(ψ t (B 0 ) -ψ t (A 0 )) -1] + j v [exp(ψ t (A 1 ) -ψ t (A 0 )) -1] = 0 ∂ t ψ t (B 0 ) + j ∆ [exp(ψ t (C 0 ) -ψ t (B 0 )) -1] + j v [exp(ψ t (B 1 ) -ψ t (B 0 )) -1] = 0 ∂ t ψ t (C 0 ) + j ∆ [exp(ψ t (A 0 ) -ψ t (C 0 )) -1] + j v [exp(ψ t (C 1 ) -ψ t (C 0 )) -1] = 0 ∂ t ψ t (A 1 ) + j ∆ [exp(ψ t (B 1 ) -ψ t (A 1 )) -1] + j v [exp(ψ t (A 0 ) -ψ t (A 1 )) -1] = 0 ∂ t ψ t (B 1 ) + j ∆ [exp(ψ t (C 1 ) -ψ t (B 1 )) -1] + j v [exp(ψ t (B 0 ) -ψ t (B 1 )) -1] = 0 ∂ t ψ t (C 1 ) + j ∆ [exp(ψ t (A 1 ) -ψ t (C 1 )) -1] + j v [exp(ψ t (C 0 ) -ψ t (C 1 )) -1] = 0 with the boundary conditions lim t→1 ψ t (B 1 ) = 0 lim t→1 ψ t (B 0 ) = lim t→1 ψ t (A i ) = lim t→1 ψ t (C i ) = -∞, i ∈ {0, 1}
The symmetric structure of the graph allows to guess the solution. It can be verified with a direct computation that

ψ t (A i ) = ψ T t (A) + ψ H t (i)
where ψ T t : (0, 1) × {A, B, C} → R is the solution of the HJB equation on the triangle (37), which is solved at (38) and ψ H t is the solution of the following HJB equation on the complete graph with two vertices (which is nothing but the discrete hypercube in dimension 1):

         ∂ t ψ H t (0) + j v [exp(ψ H t (1) -ψ H t (0)) -1] = 0 ∂ t ψ H t (1) + j v [exp(ψ H t (0) -ψ H t (1)) -1] = 0 lim t→1 ψ H t (1) = 0 lim t→1 ψ H t (0) = -∞ which
is solved in a more general form at (36). The same reasoning is valid for the calculations of ψ(B i ) and ψ(C i ). Using these explicit formulas, we obtain ψ and

j A 0 ,B 1 (t, z → z ) = exp(ψ t (z ) -ψ t (z))j(z → z ) (41)
is the explicit expression of the jump intensity j A 0 B 1 of the bridge from A 0 to B 1 . Therefore we have, for instance: Some sampler. Let us analyze in a bit more detail one example of a walk on the complete graph. Take π ∈ P(X ) a positive probability distribution on the finite set X . The detailed balance conditions: π(z)j(z → z ) = π(z )j(z → z), ∀z, z , tell us that the intensity

j A 0 ,B 1 (t, A 0 → B 0 ) = exp(ψ t (B 0 ) -ψ t (A 0 ))j ∆ = exp(ψ T t (B) -ψ T t (A) + ψ H t (0) -ψ H t (0))j ∆ = exp(ψ T t (B) -ψ T t (A))j ∆ = j ∆ exp 3 2 j ∆ (1 -t) + 2 cos √ 3 2 j ∆ (1 -t) exp 3 2 j ∆ (1 -t) + 2 sin √ 3 2 j ∆ (1 -t) -π 6
j(z → z ) = π(z ) π(z) z, z ∈ X
admits π as its reversing measure. The characteristics associated with j are

χ a [j](t, (z → z )) = x∈X π(x) 1/2 (π(z ) -1/2 -π(z) -1/2 ) χ c [j](t, c) = 1
for any 0 ≤ t ≤ 1, any arc (z → z ) and any closed walk c.

Cayley graphs. Let (X , * ) be a group and G = {g i ; i ∈ I} be a finite subset of generators.

The directed graph structure associated with G is defined for any z, z ∈ X by z → z if z = zg for some g ∈ G. We introduce the time independent reference intensity j given by

j(z → zg i ) := j i , ∀z ∈ X , g i ∈ G,
where j i > 0 only depends of the direction g i . The dynamics of the random walk R is Markov and both time-homogeneous and invariant with respect to the left translations, i.e. for all z o , z, z ∈ X , j(z o z → z o z ) = j(z → z ). For all arc (z → z ), we have χ a (z → z ) = 0 and the closed walk characteristic χ c is translation invariant.

) ∈ I n with g i 1 • • • g in = e, we have j i 1 • • • j in = k i 1 • • • k in .
As usual, we have denoted e the neutral element.

Proof. We have already seen that χ a [j] = χ a [k] = 0. On the other hand, the relation

g i 1 • • • g in = e means that c := (e → g i 1 → g i 1 g i 2 → • • • → g i 1 g i 2 • • • g i n-1 → e) is a closed walk and the identity j i 1 • • • j in = k i 1 • • • k in means that χ c [j](c) = χ c [k](c).
We conclude with Theorem 2.4, Proposition 2.7 and the invariance with respect to left translations.

Remark 5.2. If the group X is Abelian, Proposition 5.1 can be further sharpened by considering only finitely many sequences (i 1 , ..., i n ). This is done in [START_REF] Conforti | Reciprocal class of random walks on an Abelian group[END_REF]Cor. 16]. The equation (17) in [CR] corresponds to the equality of the closed walk characteristics. No mention of the arc characteristic is done, since in the case when the jump intensities are translation invariant, they are always zero.

Triangular lattice. The triangular lattice is the Cayley graph generated by g i = (cos( 2π 3 (i-1), sin( 2π 3 (i-1)), i = 1, 2, 3, and we consider a time-homogeneous and translation invariant Markov intensity j.

For any closed walk (z ↔ z + g i ) associated with an edge, we have χ c [j](t, z ↔ z + g i ) = j i j -i .

If we take any counterclockwise oriented face, i.e. a closed walk of the form ∆ z := (z → z + g 1 → z + g 1 + g 2 → z) for z ∈ X we have χ c [j](t, ∆ z ) = j 1 j 2 j 3 .

We address the question of finding another space-time homogeneous assignment {k ±i } 1≤i≤3 such that the corresponding walk belongs to R(j). Applying Theorem 2.4 and (40), or equivalently invoking Proposition 5.1, we can parametrize the solutions k as follows  

 where α, β > 0. Corollary 2.6 gives some details about the dynamics of the bridge R xy as the unique Markov walk (modulo technical conditions) that starts in x, ends in y and such that, if h > 0 is a very small duration:

k 1 = αj 1 , k -1 = α -1 j -1 k 2 = βj 2 , k -2 = β -1 j -2 k 3 = (αβ) -1 j 3 , k -3 = αβj -3
(1) At any time t and independently from the current state, it goes back and forth along the direction i during [t, t + h] with probability j i j -i h 2 /2 + o(h 2 ). (2) At any time t and independently from the current state, it goes around the perimeter of a triangular cell of the lattice in the counterclockwise sense during [t, t + h] with probability j 1 j 2 j 3 h 3 /6 + o(h 3 ). (3) If exactly one jump occurs during [t, t + h], then the density of the instant of jump is constant up to a correction factor of order o(h). This follows from χ a [j](t, z → z ) = 0 for all t and (z → z ).

Rooted regular directed tree. It is an infinite directed tree such that each vertex admits exactly m ≥ 1 offsprings. Except for the root, all vertices have the same index m + 1. It is the Cayley tree rooted at * = e and generated by G = {g 1 , . . . , g m } where these m branches are free from each other: they do not satisfy any relation (of the type g i 1 • • • g in = e). In particular, for any 1 ≤ i ≤ m, g -1 i

is not in G and in fact only a ring, instead of a group, would be necessary. This freedom is equivalent to the nonexistence of cycles which is the defining property of a tree. As a direct consequence of Proposition 5.1 we obtain the following Corollary 5.3. Two positive, time-homogeneous and translation invariant Markov intensities j and k on a rooted regular directed tree generate the same bridges: R(j) = R(k).

In particular, this implies that these bridges are insensitive to time scaling: R(αj) = R(j), for all α > 0.

The lattice Z d . The usual directed graph structure on the vertex set X = Z d is the Cayley graph structure generated by G = {g i , g -i ; 1 ≤ i ≤ d} with g i = (0, . . . , 0, 1, 0, . . . , 0) where 1 is the i-th entry and we denote g -i = -g i . As another consequence of Proposition 5.1 we obtain the following Corollary 5.4. Two time-homogeneous and translation invariant positive Markov intensities j and k on Z d generate the same bridges if only if for all 1 ≤ i ≤ d, they satisfy

j i j -i = k i k -i , ∀1 ≤ i ≤ d
where j -i and k -i are the jump intensities in the direction g -i = -g i .

Proof. This set of equalities corresponds to the identification of the closed walk characteristic along the edges. But, because the group is Abelian, it also implies the identification along the squares, which is enough to conclude with (32). Hypercube, again. Let us visit once more the hypercube X = (Z/2Z) d which is seen now as the Cayley graph generated by the canonical basis g i = (0, . . . , 0, 1, 0, . . . , 0), 1 ≤ i ≤ d, where 1 is the i-th entry. As another consequence of Proposition 5.1 we obtain the following Corollary 5.5. Two time-homogeneous and translation invariant positive Markov intensities on the hypercube generate the same bridges if only if they coincide.

Proof. The proof is the same as Corollary 5.4's one. But this time g -i = g i , so that j i j -i = k i k -i is equivalent to j 2 i = k 2 i .

Random walks with jumps of amplitude one or two. Following the proof of Corollary 5.4, it is easy to prove the following results.

Corollary 5.6. We look at random walks on Z with different rules of jumps.

(1) We consider random walks on Z seen as the Cayley graph generated by +1 and +2. Two time-homogeneous translation-invariant jump intensities k and j generate the same bridges if and only if j 2 1 /j 2 = k 2 1 /k 2 with an obvious notation.

(2) We consider random walks on Z seen as the Cayley graph generated by -1 and +2.

Two time-homogeneous translation-invariant jump intensities k and j generate the same bridges if and only if j 2 -1 j 2 = k 2 -1 k 2 with an obvious notation. Let us prove the converse statement: (a) ⇒ (b). Let u be any bounded function on X 2 and B be any X [s,t] -measurable event. We have

E P [P (B | X s , X t )u(X s , X t )] = E P [1 B u(X s , X t )] = x,y∈X π(x, y)E R xy [1 B u(X s , X t )] = x,y∈X π(x, y)E R xy [R xy (B | X s , X t )u(X s , X t )] = x,y∈X π(x, y)E R xy [R(B | X s , X t )u(X s , X t )] = E P [R(B | X s , X t )u(X s , X t )]
which implies the announced result. We have used the reciprocal property of R at the last but one equality.

  Proposition 2.1. The reciprocal class R(j) is a set of reciprocal walks in the sense of Definition 0.1, which are absolutely continuous with respect to R. Proof. By its very definition, R(j) is the subset of all convex combinations of the bridges of the Markov walk R. Remark A.3(d) tells us that any P ∈ R(j) is reciprocal. Moreover, Proposition A.1 tells us that P R because supp P 01 = supp π ⊂ supp R 01 .

  1)} is the set of all k-inactive arcs. No graph structure is associated to A 0 (P ). See Definition B.1 for the notion of closed walk. (c) We call χ [P ] = ( χ a [P ], χ c [P ]) the reciprocal characteristic of P . The term χ a [P ] is the arc component and χ c [P ] is the closed walk component of χ [P ]. (d) We often write χ [R] =: χ [j]

Proposition 2. 7 .

 7 The conclusions of Theorem 2.4 and Corollary 2.6 remain unchanged when weakening the properties (iv) by only considering closed walks c in any generating subset of the closed A ↔ (P x )-walks, see Definition B.3 and Lemma B.5. Proof. It is a direct consequence of Definition B.3 and the fact that the proofs of Theorem 2.4 and Corollary 2.6 rely on Lemma B.2.

Theorem 4. 2 (

 2 Solving the characteristic equation (29)).

Figure 1 .

 1 Figure 1. Left: an oriented triangle. Right: a non-oriented triangle

=Figure 3 .

 3 Figure 3. Decomposition of a simple walk into 2-walks and 3-walks

Figure 4 .Figure 5 .

 45 Figure 4. Two different space-time homogeneous random walks on the triangular lattice which belong to the same reciprocal class

Proposition A. 4 .

 4 For any random walk P ∈ P(Ω), the following statements are equivalent. (a) P ∈ R(j) (b) For all 0 ≤ s ≤ t ≤ 1, we haveP (X [s,t] ∈ • | X s , X t ) = R(X [s,t] ∈ • | X s , X t ), P -a.s. (43)Proof. Statement (b) with s = 0 and t = 1 is nothing but the statement (b) of Proposition A.1. Therefore, (b) ⇒ (a).

In the contexts of classical, quantum and stochastic mechanics (the latter being taken in its wide meaning including Euclidean quantum mechanics[START_REF] Chung | Introduction to Random Time and Quantum Randomness[END_REF] or hydrodynamics where the evolution is deterministic but the initial state is described by a probability measure), the term "invariant" refers to conserved quantities as time varies.

This is maybe the case for any Markov walk with finitely many jumps, but we shall not need to investigate such a general existence result.

But this doesn't imply that P is Markov. More precisely, P is Markov if and only if k x ≡ k doesn't depend on x.

CL is partially supported by the French ANR projects ANR-11-BS01-0007 -GeMeCoD and ANR-12-BS01-0019 -STAB.

Appendix A. Shared bridges

This paper is mainly concerned with mixtures of bridges such as P =

x,y π(x, y)R xy ∈ P(Ω).

(42)

Clearly, P shares its bridges with R. Next proposition gives assertions which are equivalent to this property. It is crucial for the proof of Theorem 2.4.

Proposition A.1. For any random walks P, R ∈ P(Ω) such that supp P 01 ⊂ supp R 01 , the following assertions are equivalent.

(a) P := x,y∈X π(x, y)R xy ∈ P(Ω) for some π ∈ P(supp R 01 ).

(b) P xy = R xy for all (x, y) ∈ supp P 01 .

(c) There exists a measurable function k : X 2 → [0, ∞) such that X 2 k dR 01 = 1 and

(d) There exists a measurable function h : X 2 → [0, ∞) such that for all x ∈ supp P 0 ,

Moreover, the function h at (d) is given by h

[(d) ⇒ (b)] : As supp P 01 ⊂ supp R 01 , we have

Last statement is obtained with

The identity in (d) expresses that P x is an h-transform of R x in the sense of Doob [START_REF] Doob | Conditional Brownian motion and the boundary limits of harmonic functions[END_REF].

The reciprocal property extends the notion of Markov property. Let us recall its definition and basic related general results.

Definition A.2 (Reciprocal walk). A random walk P

The reciprocal property of a path measure is defined in accordance with the usual notion related to processes. Definitions B.1 (Walk, closed walk, simple closed walk and gradient). Let A ⊂ X 2 specify a directed graph (X , →) on X with no loop. (a) For any n ≥ 1 and x 0 , . . . , x n ∈ X such that

ordered succesion of edges (x 0 , x 1 , . . . , x n ) is called an A -walk, or shortly a walk. We adopt the more appealing notation w = (

For any arc function , we denote (w) := (

Lemma B.2. Let A ↔ be a symmetric directed graph. The arc function : A ↔ → R is a gradient if and only if (c) = 0, for any closed A ↔ -walk c.

Proof. This is a standard result. If is the gradient of ψ, then (w

Choose a tagged vertex * ∈ X , set ψ( * ) = 0 and for any x = * , define

To see that this is a meaningful definition, take two paths w = ( *

, where the last equality is obtained with (45). Therefore, ψ is well defined. Finally, it follows immediately from our definition of ψ that

We introduce the notion of generating set of closed walks which turns out to be useful when deriving sharp characterizations of reciprocal classes. Let us point out that we do not ask C o to be minimal with respect to the inclusion. The whole set of closed walks C is always a generating set. Of course, the smaller C o is, the sharper is the characterization of the reciprocal class.

Any closed walk can be decomposed into a sum of simple closed walks as in Figure 6. Suppose that any simple closed walk can be decomposed as

) where F is some subset of simple closed walks and E is the set of all edges x ↔ y seen as 2-closed walks (x → y → x).