Luis Fredes

Jean-François Marckert

A combinatorial proof of Aldous-Broder theorem for general Markov chains

Aldous-Broder algorithm is a famous algorithm used to sample a uniform spanning tree of any finite connected graph G, but it is more general: given an irreducible and reversible Markov chain M on G started at r, the tree rooted at r formed by the first entrance steps in each node (different from the root) has a probability proportional to e=(e -,e + )∈Edges(t,r) M e -,e + , where the edges are directed toward r. In this paper we give proofs of Aldous-Broder theorem in the general case, where the kernel M is irreducible but not assumed to be reversible (this generalized version appeared recently in Hu, Lyons and Tang [5]).

We provide two new proofs: an adaptation of the classical argument, which is purely probabilistic, and a new proof based on combinatorial arguments. On the way we introduce a new combinatorial object that we call the golf sequences.

Introduction

Consider G = (V, E) a finite connected graph: V is the set of vertices, and E the set of undirected edges. A path is a sequence of vertices w = (w k , 0 ≤ k ≤ m), with the property that {w k , w k+1 } ∈ E for every k. This path is said to be covering if it visits all the vertices and if m is the first time with this property. More formally, for every 1

≤ k ≤ |V | define τ k (w) = inf{j, |{w 0 , • • • , w j }| = k}, 1 ≤ k ≤ |V |,
the first time the path has visited k different points (we write τ k instead of τ k (w) when it is clear from the context). The path w is then called covering if τ |V | (w) = m.

Denote by SpanningTrees(G) the set of spanning trees t of G, and by SpanningTrees • (G) the set of rooted spanning trees (t, r), where r, the root, is a distinguished vertex of V . Each tree (t, r) is considered as a directed graph in which the edges are directed toward the root: for any (e -, e + ) in the edge set E(t, r), e + is the parent of e -in t (we write e + = p(e -)).

Definition 1. For a covering path w, denote by FirstEntranceTree(w) the rooted spanning tree (t, w 0 ) whose |V | -1 edges are (w τ k , w τ k -1 ) (that is oriented towards the root w 0 ) for 2 ≤ k ≤ τ |V | .

Thus, each edge corresponds to the first edge used to visit each vertex different from w 0 , turned around.

A Markov kernel M = (M a,b , a, b ∈ V ) on V is said to be positive on G if M a,b > 0 ⇐⇒ {a, b} ∈ E. Any Markov chain driven by such a Markov kernel can traverse each edge of G both ways, and each step of such a chain corresponds to an edge of G. On a connected graph, as it is the case here, this chain is irreducible, therefore it has a unique invariant distribution, ρ = (ρ v , v ∈ V ).

A model of random covering paths is obtained by killing a Markov chain W at the cover time.

Theorem 2. [Aldous-Broder, [START_REF] Aldous | The random walk construction of uniform spanning trees and uniform labelled trees[END_REF] and [START_REF] Broder | Generating random spanning trees[END_REF]]Let W be a Markov chain with positive and reversible kernel M and invariant distribution ρ. Then, for any (t, r) ∈ SpanningTrees • (G)

P FirstEntranceTree W 0 , • • • , W τ |V | = (t, r) | W 0 = r = Const.   e∈E(t,r) M e   /ρ(r). (1)
To be totally clear, each e is an edge of the type (e -, e + ), where e + = p(e -), and M e = M e -,e + .

Elements around Aldous-Broder algorithm can be found in [START_REF] Járai | The uniform spanning tree and related models[END_REF].

As a consequence if M is the Markov kernel corresponding to the simple random walk on G, M a,b = 1 {a,b}∈E /deg G (a), and since the invariant distribution of this simple random walk ρ v is proportional to deg G (v), the r.h.s. of ( 1) is proportional to u∈V 1/deg G (u), that is independent of t, so that FirstEntranceTree(W 0 , • • • , W τ |V | ) is a uniform spanning tree 1 , rooted at W 0 = r.

As we will see, Aldous-Broder theorem does not hold if we remove the reversibility condition.

Recall that if X = (X i , i ∈ Z) is a Markov chain with positive kernel M with invariant distribution ρ, under its stationary regime, then the time reversal of X is also a Markov chain under its stationary regime, with same invariant distribution, and with kernel ← -M x,y := ρ y M y,x /ρ x , for all (x, y) ∈ V 2 .

(

) 2
The next result extends Aldous-Broder theorem:

Theorem 3. Let W be a Markov chain with positive kernel M (reversible or not) with invariant distribution ρ. Then, for any (t, r) ∈ SpanningTrees • (G)

P FirstEntranceTree W 0 , • • • , W τ |V | = (t, r) | W 0 = r = Const.   e∈E(t,r) ← - M e   /ρ(r). (3)
The aim of this paper, is to give two new proofs of this result. This theorem has been proved by Hu, Lyons and Tang [START_REF] Hu | A reverse Aldous-Broder algorithm[END_REF] shortly before our work; but, at the moment we were writing the present paper, this result was not present on the first version of [START_REF] Hu | A reverse Aldous-Broder algorithm[END_REF], on the arxiv.

• This theorem implies Aldous-Broder result since in the reversible case, ← -M = M . • We will prove that if W is taken under its stationary regime (meaning that W 0 ∼ ρ) then

P FirstEntranceTree W 0 , • • • , W τ |V | = (t, r) = Const.   e∈E(t,r) ← - M e   . ( 4
)
This formula is equivalent to (3).

• From our point of view, Aldous-Broder theorem should be stated like Theorem 3, since this time reversal is not only a tool for the (original) proof of the Theorem but a characteristic of its conclusion. As a matter of fact, it is probably common for researchers in the field to try to find a coupling between Wilson construction [START_REF] Wilson | Generating random spanning trees more quickly than the cover time[END_REF][START_REF] Propp | How to get a perfectly random sample from a generic markov chain and generate a random spanning tree of a directed graph[END_REF] of the spanning tree (which is faster) and Aldous-Broder's, but the fact that Wilson algorithm produces a tree with distribution Const. e∈E(t,r) M e shows that it is likely not possible, unless ones use Wilson algorithm with ← -M instead of M .

• Both theorems above are valid on multigraph, which are the analogous of graph in which multiple edges between vertices are allowed, as well as loops (edges {a, a} adjacent to a single node are allowed).

All the proofs we give are valid in this settings too (even if tiny adjustments to treat multiple edges could be needed at some places).

Remark 4. In general, e∈E(t,r) M e and e∈E(t,r) ← -M e are different. Let us write u∈t for a product over the set of vertices of t. For (t, r) ∈ SpanningTrees • (G),

e∈E(t,r) M e = u∈t\{r} M u,p(u) = Const. ρ r u∈t\{r} ρ u M u,p(u)
while by [START_REF] Broder | Generating random spanning trees[END_REF], and since in a tree all nodes but the root are children of some nodes,

e∈E(t,r) ← - M e = u∈t\{r} M p(u),u ρ p(u) /ρ u = Const. ρ r u∈t\{r} ρ p(u) M p(u),u .
so that these quantities are different when ρ is not reversible with respect to M .

Different formula does not imply different values, but a graph of size 3 is sufficient to observe that these formulas are indeed different: consider It can be verified that ρ is the invariant measure of M and that ← -M is the reversal kernel. The tree (t, r) defined by (2, 1) and [START_REF] Cartier | Problèmes combinatoires de commutation et réarrangements[END_REF][START_REF] Aldous | The random walk construction of uniform spanning trees and uniform labelled trees[END_REF]

M =    0 1/3 2/
has weights M 2,1 M 3,1 = 1/35 = ← - M 2,1 ← - M 3,1 = 121/4655.
Let us say some words on the paths (w k , 0 ≤ k ≤ τ |V | ) that satisfy FirstEntranceTree w 0 , • • • , w τ |V | = (t, r). Such a path starts at w 0 = r and eventually reaches each vertex u of V \ {r} for the first time from p(u) its parent in (t, r). In other words, FirstEntranceTree w 0 ,

• • • , w τ |V | = (t, r) iff {(w τ k , w τ k -1 ), 2 ≤ k ≤ |V |} = {(u, p(u)), u ∈ V \ {r}}, (5)
meaning that k → w(τ k ) induces a decreasing labelling towards the root. The analysis of P(FirstEntranceTree W 0 , • • • , W τ |V | = (t, r)) from this kind of considerations leads to sum on all the paths according to the order at which the vertices are reached. Since this direct approach of Theorem 3 seems difficult to complete, the initial proofs by both Aldous and Broder of their theorems follow a tricky path which is purely probabilistic. In our new proof, we avoid also the direct treatment of the labellings discussed above, but produce instead a combinatorial argument, relying on a new object we introduce, the golf sequence, which, we believe is interesting in its own.

Some recalls from combinatorics

The new proof uses many ingredients of the combinatorics folklore, and we must say that we have been deeply inspired by Zeilberger short paper [START_REF] Zeilberger | A combinatorial approach to matrix algebra[END_REF] where many results from linear algebra are proved by means of combinatorial tools, notably, Foata's proof of MacMahon's master theorem [START_REF] Zeilberger | A combinatorial approach to matrix algebra[END_REF][START_REF] Cartier | Problèmes combinatoires de commutation et réarrangements[END_REF] and the famous Theorem 5 (Matrix Tree Theorem).

det(Id -M (r) ) = (t,r)∈SpanningTrees • (G) e∈E(t,r) M e , (6)
where M (r) is the matrix M deprived of the line r and column r, and Id the identity matrix with the same size as that of M (r) .

We borrow the argument from Zeilberger [START_REF] Zeilberger | A combinatorial approach to matrix algebra[END_REF] since it helps to present the arguments of our own proof.

Proof. First, a cycle is a (class of equivalence of) path (w 0 , • • • , w m ) for some m ≥ 1, such that w m = w 0 and |{w 0 , • • • , w m }| = m (it is simple). Two cycles are equivalent if one can be obtained from the other by shifting its indices in Z/mZ. Observe that

Id -M (r) = v ∈V M u,v 1 (u=v) -M u,v (u,v)∈(V \{r}) 2 . ( 7
)
Denote by B the set of pairs (B, C) such that:

• B is a directed graph on V , where each vertex of V \ {r} has either 0 or 1 outgoing edge ending in V (including {r} this time). Denote by V B the set of vertices from which there is an outgoing edge.

• C is a collection of directed disjoint cycles on An expansion of (7) allows one to see that Weight(B) :

V C = (V \ {r}) \ V B . Set Weight(B) := u∈V B M u,t (
= (B,C)∈B Weight(B, C) = det(Id -M (r)
). Here is the argument: first, expand det(Id -M (r) ) using Leibniz formula:

det(Id -M (r) ) = (-1) sign(σ) i =r (Id -M (r) ) i,σ(i) ,
where the sum range on all permutations σ on V \ {r}. Now, consider the set F (σ) = {i : σ(i) = i} of fix points of σ, and rewrite, by [START_REF] Krattenthaler | The theory of heaps and the cartier-foata monoid[END_REF]:

i =r (Id -M (r) ) i,σ(i) =   i∈F (σ)   -M i,i + j∈V M i,j       i∈V \({r}∪F (σ)) -M i,σ(i)   .
The second parenthesis can be interpreted as the weight of cycles of σ with lengths at least 2. Now expand the first parenthesis (without simplifying M i,i , so that M i,i comes with a sign +, and in another term, with a sign -). This first parenthesis can be rewritten as a sum over A ⊂ F (σ) as follows:

i∈F (σ)   -M i,i + j∈V M i,j   = A⊂F (σ) i∈A (-M i,i )   i∈F (σ)\A j M i,j   .
Each factor -M i,i can be seen to be the weight of a loop over i (that is a cycle of size 1), and by expansion, i∈F (σ)\A j∈V M i,j can be interpreted as the weight of a directed graph where each vertex of F (σ) \ A has a single outgoing edge, ending on any vertex of V . This ends the argument explaining why Weight(B) = det(Id -M (r) ).

-We claim now that Weight(B) = (t,r)∈SpanningTrees • (G) e∈E(t,r) M e . The graphs "B" are made of cycles and trees, and C is made of cycles (with a sign of the weight corresponding to parity). For any pair (B, C) having (totally) at least one cycle one can define (B , C ) as follows: for a total order on the set of oriented cycles, take the greatest cycle c in the union of B and C. Denote by (B , C ) the pair obtained by moving c from the component containing it to the other. This map (B, C) → (B , C ) is clearly an involution and satisfies Weight(B , C ) = -Weight(B, C). Hence, Weight(B) coincides with the sum of the Weight(B, C) taken on the set of pairs (B, C) which have no cycles: C is empty, and the graph B has no cycle, and since its number of edges is one less than its number of vertices, it is a spanning tree.

The quantity det Id -M (r) is the central algebraic object; it is somehow the partition function of the family of weighted spanning trees under inspection, but not only. It will appear under the following forms at several places of the paper.

Notice that the direct expansion of the determinant (using permutations) gives

det(Id -M (r) ) = C (-1) N (C) c cycles of C e∈c M e (8)
where the sum ranges over all sets C of disjoint (oriented) cycles of length ≥ 1 on the set of vertices V \ {r}. Now by considering the involution that changes the orientation of every cycle one gets

det(Id -M (r) ) = det(Id - ← - M (r) )
and therefore for a fixed r ∈ V

(t,r)∈SpanningTrees • (G) e∈E(t,r) M e = (t,r)∈SpanningTrees • (G) e∈E(t,r) ← - M e .
This together with Remark 4 say that even though the terms associated to each tree (t, r) may be different, these sums are equal (similar identities are present in Hu & al. [START_REF] Hu | A reverse Aldous-Broder algorithm[END_REF]).

Even more, the invariant distribution ρ of the Markov kernels M and ← -M is related to these quantities by:

ρ w = Const. det(Id -M (w) ) = Const. det(Id - ← - M (w) ) (9)
so that, from the matrix tree theorem, this provides a connection between ρ w and the total mass of spanning trees rooted at w. To prove [START_REF] Viennot | Heaps of pieces, i : Basic definitions and combinatorial lemmas[END_REF], there are several methods, one of them being the use of Theorem 2 or 3, but direct arguments exist (and are classical). One wants to solve the vector system

ρ(Id -M ) = 0, ρ 1 . . . 1 = 1 .
Assume here that the vertex are labeled from 1 to n. Since the sum by rows of Id -M is zero, the system is over-determined, so we discard the equation (ρ(Id -M )) 1,n = 0. Then, the row vector ρ is solution of

ρQ = 0 • • • 0 1 where Q =    (Id -M ) i,j i≤n,j≤n-1 1 . . . 1    . (10)
By symmetry, it suffices to prove that ρ n satisfies [START_REF] Viennot | Heaps of pieces, i : Basic definitions and combinatorial lemmas[END_REF]. For this use the Cramer rule to get (9): notice that replacing the n-th row of Q by [0, • • • , 0, 1] we obtain the wanted determinant in the numerator (as a cofactor). It remains to show for the denominator that det(Q) = w det(Id -M (w) ); the following argument is classical. It suffices to expand det(Q) according to the last column and show that det((Id -M ) (i,j):i =a,j =n )(-1) n-a = det((Id -M ) (i,j):i =a,j =a ) = det(Id -M (a) ). [START_REF] Zeilberger | A combinatorial approach to matrix algebra[END_REF] This first equality is more general: in fact, det((Id -M ) (i,j):i =a,j =b )(-1) b-a = det((Id -M ) (i,j):i =a,j =a ) for all b ∈ {1, • • • , n}, and this independence to the deprived column b (up to the sign) is a consequence of the fact that the sum of the columns of Id -M is 0 (this property allows to play with the lacking column b: take the a-th column C a and replace it by

C a + k =a,b C k = k =b C k = -C b .
This replacement does not alter the determinant, and now, we have -C b at position a).

New combinatorial proof of Theorem 3

We will assume all along the proof that |V | ≥ 2, otherwise the statement is trivial. Theorem 3 expresses P(FirstEntranceTree

(W i , 0 ≤ i ≤ τ |V | (W )) = (t, r)) in terms of ← - M , but
Weight(w) := |w|-1 i=0 ← - M w i+1 ,w i , (12)
which is the weight of ←w starting at w taken under the kernel

← - M . A heap h of directed outgoing edges of a vertex u is a finite sequence h = [(u, t i ), 1 ≤ i ≤ ]
for some ≥ 0, where, for each i, {u, t i } ∈ E. The set of such heaps is ∪ k≥0 O k u where O u = {(u, v) : {u, v} ∈ E} is the set of oriented outgoing edges out of u (in G). A collection of heaps is a sequence

H := (H u , u ∈ V ) of heaps, where H u ∈ ∪ k≥0 O k
u is a heap of directed edges out of u (see Fig. 1, picture 2). The set of collections of heaps is the product set

HeapCol = u∈V k O k u .
Each element of HeapCol can be seen as a multigraph (repetition of edges permitted), in which the sequence of outgoing edges out of each node is equipped with a total order. We will use collections of heaps to encode various sorts of family of connected paths. As a combinatorial tool, they allow some rearrangements of steps, and then provide some ways to construct bijections efficiently.

The concatenation operation ⊕ of heaps is defined as usual:

[e 1 , • • • , e m ] ⊕ [e 1 , • • • , e m ] = [e 1 , • • • , e m , e 1 , • • • , e m ]
which extends to collection of heaps as expected :

H ⊕ H := (H u ⊕ H u , u ∈ V ).
We say that h is a prefix of h ⊕ h , notion which extends again to collections.

The weight of a heap

h = [(s i , t i ), 1 ≤ i ≤ m] and of a collection H = (H u , u ∈ V ) are Weight(h) := m i=1 ← - M s i ,t i , Weight(H) := u∈V Weight(H u ).
The weight of an empty heap is set to 1.

Prefix removal (PR). For h = h ⊕ h , the "prefix removal" of h in h is possible. We write this operation h P R h = h . This extends to collections: if H = H ⊕ H , we set

H P R H = H .
Trees. The number of children Deg in (t,r) (u) of a node u in (t, r) which is often called out-degree or simply degree in the literature in the case of trees, coincides with the number of incoming edges at u in (t, r) (the notation Deg in (t,r) (u) is introduced to avoid any confusion with deg G (u), the degree of the graph at u which comes into play too, and with the total degree of u in t). A node u with Deg in (t,r) (u) = 0 is called a leaf, and the set of leaves is denoted ∂t. Notice that since |V | ≥ 2, r is not a leaf. The elements in the set t o = V \ ∂t are called internal nodes.

Step 1. Collection of heaps encoding of a path

Definition 6. The passport of a collection of heaps H = (H u , u ∈ V ) ∈ HeapCol is the pair

OUTIN(H) := [(Out u (H), u ∈ V ), (In u (H), u ∈ V )]
where, for all u ∈ V , Out u (H) := |H u | records the number of outgoing edges of u and

In u (H) := w∈V |(w, u) in H w |
records the number of incoming edges to u (with multiplicities).

As a standard passport in real life, the passport is used to record the number of entries/exits at each node, with multiplicities. Different collections of heaps can have the same passport.

Denote by Paths(r) the set of paths w starting at w 0 = r (with any finite length). With any path w ∈ Paths(r) associate the collection of heaps Heap(w) := (Heap u (w), u ∈ V ) ∈ HeapCol, where Heap u (w) := [(w j+1 , w j ) : 0 ≤ j ≤ |w| -1, w j+1 = u] ; these edges are then taken according to their order in w, and they correspond to edges that reach u, that are turned around. It can be useful to consider them as steps outgoing from u in ←w , still taken according to their order in w (see Figure 1).

As warm up, let us prove the following classical fact. This is not a bijection since some elements of HeapCol do not encode any paths.

Proof. Let us take an element h = (h u , u ∈ V ) in the image, and let us reconstruct its unique preimage w by the map Heap (in fact, we build ←w ). The total number of edges in h is the number of steps m of any walk w such that Heap(w) = h. If m = 0, the statement is clear. Recall that the collection of heaps gives the steps of ←w . Assume m > 0. This allows to recover the only possible value for the final point w m too: this is the unique node w m having one more outgoing edge than incoming (if such a node does not exist, the path ends and starts at r, and then w m = r). Now, knowing the last position of the walk w m , take (w m , u) the rightmost (top see Figure 1) edge in Heap wm , record the identity of the node u, and remove the edge (w m , u) from Heap wm . Now, set w m-1 := u. Iterate the construction until all the heaps are empty. The statement about the weights easily follows.

v 0 v 1 v 2 v 3 v 4 v 5 v 6 v 2 v 6 v 5 v 4 v 1 v 3 v 0 Figure 1: Left: graph G, where the walk w = v 0 v 3 v 0 v 1 v 0 v 1 v 0 v 3 v 0 v 3 v 4 v 5 v 4 v 6 v 4 v 3 v 4 v 5 v 2 is performed.
Right: Heap associated to the path w; for example,

H v 3 = [(v 3 , v 0 ), (v 3 , v 0 ), (v 3 , v 0 ), (v 3 , v 4 )].
To read the steps of w in the heap, follow the edges from top to bottom to form ←w , then transform ←w into w. The steps used to construct the tree are circled. Definition 8. (i) A collection of heaps H ∈ HeapCol with a balanced passport i.e.

OUTIN (H) = [(N u , u ∈ V ), (N u , u ∈ V )], (13)
for some N u ≥ 0, is called a heap of cycles. Denote by HCycles the set of heaps of cycles and by HCycles(free v) the heaps of cycles where N v = 0, meaning that v is not an element of any cycle.

(ii) A heap of cycles H ∈ HCycles satisfying N u ≤ 1 for all u, is called trivial (it is a set of non intersecting cycles). We denote by HCycles Trivial (free v) the set of trivial heap of cycles for which N v = 0 (that is, non incident to v).

Remark 9. It is folklore to build "classical heap of cycles" from "our collection of heaps with balanced passport" see Viennot [START_REF] Viennot | Heaps of pieces, i : Basic definitions and combinatorial lemmas[END_REF]. Classical heaps of cycles are equivalence classes of sequence of cycles (c 1 , • • • , c p ) (were p ≥ 0), where the relation is the transitive closure of the following relation: two

sequences (c 1 , • • • , c p ) ∼ R (c 1 , • • • , c p )
are equivalent if they coincide except for some non intersecting and consecutive cycles c i and c i+1 and (c i , c i+1 ) = (c i+1 , c i ). In words: non intersecting cycles commute, and intersecting cycles do not. Following Cartier & Foata [START_REF] Cartier | Problèmes combinatoires de commutation et réarrangements[END_REF] terminology, sequences of cycles with the partial commutation formula form a partially commutative monoid (for the concatenation operation), which can be geometrically represented using heap of "real" cycles (see Viennot [START_REF] Viennot | Heaps of pieces, i : Basic definitions and combinatorial lemmas[END_REF] and Krattenthaler [START_REF] Krattenthaler | The theory of heaps and the cartier-foata monoid[END_REF]).

Giving these classical heap of cycles one can form the collection of heaps Heap(c 1 ) ⊕ • • • ⊕ Heap(c p ). To define the converse we need to introduce first, the PopCycle function. Assume that a collection of heaps (H u , u ∈ V ) is given. For a vertex w 0 we define the procedure PopCycle(w 0 ) as: follow the path starting at w 0 and stop it the first time it forms a cycle c, that is the path w 0 , w 1 , • • • , w j satisfies w i = w j for some i < j and j is the first index with this property; then return c the cycle formed by (w i , • • • , w j ) and suppress the cycle from the heaps (that is all the edges (w i , w i+1 ), • • • , (w j-1 , w j )). Now, to define the converse do the following: if all the heaps of the collection are empty, then associate the empty heap of cycles; otherwise, consider w 0 = u a vertex with non-empty heap. Starting from i = 1 repeat the following procedure until the heaps are all empty: define c i := PopCycle(w 0 ), increment i and define w 0 = u, for a u chosen among those for which H u = ∅ (see Figure 2 for a representation of this map). This procedure is well-defined since passports are balanced, i.e. the number of incoming edges is equal to the number of out-coming edges; and this property is preserved each time PopCycle is used. At the end, the sequence (c 1 , • • • , c m ) obtained depends on the order of the nodes u chosen, but it can be proved that for all choices of u, the final sequences of cycles are equal as heap of cycles.

v 2 v 6 v 4 v 1 v 0 v 3 v 5 v 2 v 6 v 4 v 1 v 0 v 3 v 5 v 2 v v 4 v 1 v 0 v 3 v 5
Figure 2: Left: representation of a heap of cycles as in Definition 8. Center: algorithm to form the classical heap of cycles started from v 3 . Right: representation of a classical heap of cycles (there are some cycles on top of the others). Cycles here have length 2, but they may be of any length in general.

For a trivial heap of cycles H = (H u , u ∈ V ), define

SignedWeight(H) = Weight(H)(-1) |Cycles(H)| .

We have the following inversion formula

H∈HCycles(free f )

Weight(H) =   H∈HCycles Trivial (free f ) SignedWeight(H)   -1 (8) = det Id -M (f ) -1 . ( 14
)
This formula is famous in combinatorics (see [START_REF] Viennot | Heaps of pieces, i : Basic definitions and combinatorial lemmas[END_REF][START_REF] Krattenthaler | The theory of heaps and the cartier-foata monoid[END_REF]). A simple proof : we will prove that the product of the sums of the two first members of (14) gives 1. For this associate to each pair (h, t) of heap of cycles and trivial heap of cycles (an element of HCycles(free f ) × HCycles Trivial (free f )), a pair (h , t ) of the same type obtained as follows: Take the greatest cycle c in the union of t and of the set of cycles of h having no cycle above them and which moreover do not intersect the cycles of t. Now, to obtain (h , t ) from (h, t), remove c from the component which contains it, and move it to the other (if it is move on h, it is placed on top of it). This operation is an involution which changes the sign of the weight, so that the total weight of the pairs (h, t) coincides with the weight of the single pair (∅, ∅) which is 1.

Step 2. Collection of heaps of a covering path corresponding to a given tree

Consider the subset of Paths(r), Paths(t, r, f ) := {w covering : FirstEntranceTree(w) = (t, r), w = r, w = f }.

The passport of any path w ∈ Paths(t, r, f ), satisfies,

OUTIN(Heap(w)) = [(N u + 1 u=f , u ∈ V ), (N u + 1 u=r , u ∈ V )], (15)
for N f = 0, some N r ≥ 0, and some N u ≥ 1 for all u / ∈ {f, r}. From the FirstEntranceTree construction, the last visited vertex is a leaf: Lemma 10. If f is an internal node of t, then Paths(t, r, f ) = ∅.

All paths w ∈ Paths(t, r, f ) have a step from p(u) to u, for each node u = r. The oriented edges of (t, r) can be seen as a collection of heaps H t = (H t u , u ∈ V ) defined by:

H t u = [(u, p(u)], for u = r, H t r = ∅, whose passport is OUTIN(H t ) = (1 -1 u=r , u ∈ V ) , Deg in (t,r) (u), u ∈ V . ( 16
)
By construction, the edges of H t are the first edges of the collection Heap(w) (we put them according to their order in w), and then can be removed using the remove prefix operation; it produces the collection of "truncated heaps" defined by removing the edges of t from Heap(w)

Heap Trunc (w) := Heap(w) P R H t (w). ( 17)

If (15) holds, in view of ( 16), the passport of Heap Trunc (w) is

OUTIN Heap Trunc (w) = [(N u + 1 u=f -(1 -1 u=r ), u ∈ V ), (N u + 1 u=r -Deg in (t,r) (u), u ∈ V )]. ( 18
)
One of the main point of the proof is the following Lemma, which says that we completely know the set of collections of truncated heaps Heap Trunc [Paths(t, r, f )]. In words, they correspond, prior to truncation, to all collections Heap(w) satisfying (15) and large enough so that H t can be removed. Set

HeapCol[(o u , u ∈ V ), (i u , u ∈ V )] := {h ∈ HeapCol : OUTIN(h) = [(o u , u ∈ V ), (i u , u ∈ V )]} Lemma 11. If f ∈ ∂t, the set Heap Trunc [Paths(t, r, f )] is equals to Ξ(t, r, f ) := HeapCol (n u + (Deg in (t,r) (u) -1)1 u∈t o , ∈ V ), (n u + 1 u∈∂t (1 -1 u=f ), u ∈ V ) (19)
where the union is taken on all n u ≥ 0, ∀u = f , and n f = 0 (no incoming or outgoing edge at f , while n u + 1 u∈∂t (1 -1 u=f ) > 0 for the other leaves).

Lemma 11 describes the set of heaps that are not circled in Figure 1 (in all generality).

Proof. Proof of Heap Trunc [Paths(t, r, f )] ⊂ Ξ(t, r, f ). This inclusion can be seen thanks to a change of variables from (18). Indeed, from (18) we must have N u -Deg in (t,r) (u) + 1 u=r ≥ 0 and N u + 1 u=f -1 + 1 u=r ≥ 0, which implies

N u ≥ Deg in (t,r) (u) -1 u=r 1 u∈t o + 1 u∈∂t (1 -1 u=f )
since Deg in (t,r) (u) ≥ 1 when u ∈ t o and Deg in (t,r) (u) = 0 when u ∈ ∂t. We then set

n u := N u -Deg in (t,r) (u) -1 u=r 1 u∈t o + 1 u∈∂t (1 -1 u=f )
and compute the passport (18) after this change of variable to conclude this inclusion. Now, take h This construction stops when a vertex p with an empty heap H p is reached. To conclude the proof, taking into account Lemma 7, it suffices to prove that all the heaps are empty when this event occurs (since it is necessary and sufficient for H to encode a path).

= (h u , u ∈ V ) ∈ Ξ(t,
We claim that indeed, all the heaps are empty and moreover p = r. Observe first that the global passport of H is obtained by doing OUTIN(H t ) + OUTIN(h), which gives for some (n u , u ∈ V ),

(n u + (Deg in (t,r) (u) -1)1 u∈t o + 1 -1 u=r , u ∈ V ), (n u + Deg in (t,r) (u) + 1 u∈∂t (1 -1 u=f ), u ∈ V ) = (n u + Deg in (t,r) (u) + 1 u∈∂t -1 u=r , u ∈ V ), (n u + Deg in (t,r) (u) + 1 u∈∂t -1 u=f , u ∈ V ) .
Up to a change of variables, this matches the passport of a path (see ( 15)); however (15) does not characterize collection of heaps corresponding to paths, but collection of heaps of paths concatenated with heap of cycles (see Defi. 8 and ( 13)). We then need to discard the possibility of cycles. Notice that each vertex different from r has as many outgoing as incoming edges, so that necessarily p = r. We will prove that if the heap H v of an internal node v is empty, then it is also the case of the heaps of its children. Indeed, if H v is empty, then, all the outgoing edges out of v have been used, and therefore all the incoming edges to v must have also been used too! (one always needs to enter before exiting).

Therefore when H v is empty all the incoming edges arriving at v have been used in their respective heaps. As a matter of fact, the leftmost edge of the heap H u for each child u of v, is the edge (u, v), and this edge is incoming at v: as a conclusion when H v is empty, H u is empty too.

By Lemma 11, Corollary 12. For any (t, r) ∈ SpanningTrees • (G),

P(FirstEntranceTree(w 0 , • • • , w τ |V | (w) ) = (t, r)) = Weight(H t ) f ∈∂t ρ f Weight(Ξ(t, r, f )) = e∈E(t,r) ← - M e f ∈∂t ρ f Weight(Ξ(t, r, f )).

The combinatorial trick

In the preceding sections we use collections of heaps to present some operations that could have been presented without them, since withdrawing the steps of the first entrance trees could have been done directly on w. From here, collections of heaps becomes the central objects: just consider a moment the collections of heaps Heap Trunc (w) which comes from w, and have been defined using t. From now on, the economic way to think about them is to forget where they come from ! They are just elements (H u , u ∈ V ) of some sets of collections of heaps whose passports satisfy some constraints (see Proposition 16). When seen as coming from w and ←w , it is tempting to equip the edges of (H u , u ∈ V ) with a global order inherited from w, but this way of thinking drove us in some dead ends.

Collections of heaps are simple object, devoid of global ordering, even if each heap comes with a fixed order. In the sequel, in order to make clear that we don't try to follow in any way the order induced by w, we still call "first edge" of H u the leftmost one (the bottom on the figures in the representation of heaps, for example, Figure 1). All our algorithms will use "first edges first": hence since the edges of t have been removed, following paths constructed using the first edges of the heaps produce paths that do not correspond to portions of w or of ←w in general. The general principle is that one can do many things with collections of heaps. Including playing golf? Yes.

Combinatorial golf sequences decomposition

In the sport called golf, players hit balls into a series of holes. We introduce the combinatorial golf sequence, a new combinatorial object: it consists in a sequence of paths on G, modeling the moves of some balls (placed on some vertices) on a golf court (the graph G), until each of them finds a different empty hole (some special vertices). It is parameterized by the pair HoleSet, S as follows:

• S = (S 1 , • • • , S Nb
) is the sequence of starting vertices from which balls are to be played, with S j , being the starting position of the j-th. We denote by Nb u := |{j : S j = u}| the number of balls starting at u, Nb = u Nb u , the total number of balls; (Nb u , u ∈ V ) is called the counting sequence of S.

• HoleSet is a subset of V , the set of empty holes, and we require u ∈ HoleSet ⇒ Nb u = 0 so that a node which is the ending point of a path, is not the starting of any paths. Definition 13. A sequence of paths (w (1) , • • • , w (|Nb|) ) is an element of GolfSequence HoleSet, S iff:

-for any j, w (j) = w (j) i , 0 ≤ i ≤ w (j) is a finite path starting at S j , i.e. w (j) ∈ Paths(S j ), -the final positions of each path is a hole, meaning that Final(i) := w (i) (|w (i) |) ∈ HoleSet, for all 1 ≤ i ≤ Nb.

-each hole captures the first ball visiting it, and looses after that the property of being a hole. It becomes a standard vertex for subsequent paths. This means that the vertices Final(i) are distinct, and:

• the time |w (1) | is the hitting time of HoleSet by w (1) - -----------The stochastic golf sequence. We call StochasticGolfSequence HoleSet, S , a random variable X := (X (1) , • • • , X (Nb) ) taking its values in GolfSequence HoleSet, S distributed as follows. For any j ∈ {1, • • • , Nb}, conditionally on {X (1) , • • • , X (j-1) }, the trajectory of the jth ball X (j) := (X (j) t , t ≥ 0) is a Markov chain with kernel ← -M started at S j and killed at the first element of HoleSet not present in the already killed trajectories (X (k) , k ≤ j -1).

------------The weight of a combinatorial golf sequence (w (1) , • • • , w (Nb) ) is set as Weight w (1)

, • • • , w (Nb) := Nb j=1 Weight w (j) = Nb j=1 |w (j) |-1 i=0 ← - M w (j) i ,w (j) i+1
which then corresponds to the probability of independent trajectories in the stochastic golf sequence using the kernel ← -M , killed at the first time it visits a still available hole. Denote by GolfSequence HoleSet, S, free f the subset of GolfSequence HoleSet, S leaving the hole f empty, meaning that f ∈ {Final(i), 1 ≤ i ≤ Nb}).

Proposition 15. [Trivial stochastic golf sequence property] Let X = (X (1) , • • • , X (Nb) ) be a StochasticGolfSequence HoleSet, S with Nb ≤ |HoleSet|.

(i) We have P X ∈ GolfSequence HoleSet, S = 1.

(ii) If Nb = |HoleSet| -1 (eventually a single hole will remains free with probability 1) then

f ∈HoleSet P X ∈ GolfSequence HoleSet, S, free ∈ f = 1.
Proof. When Nb ≤ |HoleSet|, the stochastic golf sequence is well defined and takes its value in GolfSequence HoleSet, S : the paths are a.s. finite by irreducibility of the Markov chains. The second statement follows since a single hole must remain free at the end.

Proposition 16. For any parameters (HoleSet, S) such that u ∈ HoleSet ⇒ Nb u = 0, the map Heap : GolfSequence HoleSet, S -→ HeapCol

w (1) , • • • , w (Nb) -→ Heap w (1) ⊕ • • • ⊕ Heap w (Nb) (20)
is a weight preserving injection, and the image is included in

A:|A|=Nb A⊂HoleSet nu≥0 HeapCol [(n u + Nb u , u ∈ V ), (n u + 1 u∈A ), u ∈ V )] (21)
Remark 17. This Proposition is also a key point of our approach. The map w (1) , ) is not an injection when defined on a more general set of Nb-tuple of paths; but for golf sequences, it is.

• • • , w (N ) → Heap w (1) ⊕ • • • ⊕ Heap w (N
Proof. The fact that the image of any golf sequence is included in (21) comes from the fact that for each u, Nb u paths start at u. The result is that, eventually, a subset A of the HoleSet with cardinality Nb is eventually occupied. This gives a collection of heaps in the set (21). Take H := Heap w (1) ⊕ • • • ⊕ Heap w (Nb) an image under this map. It suffices to explain how to recover w (1) from H (and iterate). Recall that S 1 and HoleSet are known data. To recover w (1) follow steps (a), (b) and (c) in Lemma 11 started at p = S 1 with the difference that we stop and return the path the first time p ∈ HoleSet and then we define Final(1) := p. Do the same for w (k) , except that the stopping time is now the first time the constructed path hits HoleSet \ {Final(1), • • • , Final(k -1)}. At the end, the set of final points A is the set of final points of the golf paths.

Decomposition of Truncated heaps

Proposition 18. Consider (Nb u , u ∈ V ) some non negative integers, HoleSet a subset of V , such that |HoleSet| = Nb + 1, and such that u ∈ HoleSet ⇒ Nb u = 0,

f = v 2 v 6 ∈ HoleSet S 1 = v 4 v 1 ∈ HoleSet S 2 = v 0 v 2 ∈ HoleSet
Figure 3: An application of Proposition 18 to our example in Figure 1. The bijection takes as input a pair of heaps: the heap of cycles is in red, and the golf sequence heap is colored blue and purple blue steps shows the path starting at S 1 = v 4 and the purple steps the path starting at S 2 = v 0 ; in this case S = (S 1 , S 2 ) = (v 4 , v 0 )). The bijection outputs the heap obtained by putting the heap of cycles above the golf sequence heap. The corresponding HoleSet is {v 1 , v 2 , v 6 }, and f = v 2 (it is in free, because it belongs to HoleSet, and there are not incoming edges at v 2 ). We kept the steps used to construct the tree, which are circled, in order to show the full decomposition of Figure 1.

i.e. after the golf sequence a single vertex remains free. Finally let S = (S 1 , • • • , S Nb ) be a sequence of starting points with counting vector (Nb u , u ∈ V ). Assume that f ∈ HoleSet. There is a weight preserving bijection between N := HeapGolfSequence HoleSet, S, free f × HCycles(free f ) and

M := nu≥0 n f =0 HeapCol (n u + Nb u , u ∈ V ), (n u + 1 u∈HoleSet\{f } ), u ∈ V ) .
See Figure 3 for an application of this proposition.

Proof. The map φ : (H 1 , H 2 ) → H 1 ⊕ H 2 is an injection from N to M since passports are compatible, and as following the idea in the proof of Proposition 16 (in the case where |A| = Nb -1), it is possible to recover the golf sequence from the concatenation. Now, φ is also a surjection: take an element H ∈ M and let us build a pair (h, h ) ∈ N such that h⊕h = H. For that, we need to show that we can extract from H all the golf trajectories. Consider S 1 , and follow the path coming out of S 1 using the edges given by the collection H, as usual. Eventually, this path will reach an element z of HoleSet: indeed, for all nodes which are not in HoleSet, the number of outgoing edges is ≥ the number of incoming edges. It is then not possible that the ball arriving at an internal node u ∈ t o , find an empty heap H u and is trapped there.

This gives the first golf sequence, and the removal of all the edges used to define it provides an element of n u ≥0 n f =0

HeapCol (n u + Nb u -1 u=S 1 , u ∈ V ), (n u + 1 u∈HoleSet\{f,z} ), u ∈ V ) since the balance at each vertex of this first path is 0, except at the starting and ending position. We are in the same situation as before with one less path in the golf sequence. When all the paths of the golf sequence have been extracted, the possibly remaining heaps are balanced, and still n f = 0, so that the remaining steps form a heap of piece of HCycles(free f ).

The equality in law ( 23) is crucial: assume that (X k , k ≥ 0) is a Markov chain with kernel M ; in this case the initial value X 0 , play a role for (X k , k ≥ 0), which is really different from the final value

(X 0 , X 1 , X 2 , • • • ) (d) = (Y 0 , Y -1 , Y -2 , • • • ) (b) If M is reversible (that is M = ← - M ) then, if (X k , k ∈ Z)
and (Y k , k ∈ Z) are two Markov chains with respective Markov kernel M , then for any x 0 ,

L [(X 0 , X 1 , X 2 , • • • ) | X 0 = x 0 ] = L [(Y 0 , Y -1 , Y -2 , • • • ) | Y 0 = x 0 ]
(so that, somehow, the situation of (a) occurs, conditionally, "outside the stationary regime").

Aldous-Broder argument relies on (b) while (a) seems to us more natural and leads to Theorem 3. The following Lemma is not stated by Aldous [START_REF] Aldous | The random walk construction of uniform spanning trees and uniform labelled trees[END_REF] or Broder [START_REF] Broder | Generating random spanning trees[END_REF], but it is a consequence of their proofs.

Lemma 24. Assume (Y k,k∈Z ) is a Markov chain with kernel ← -M under its stationary regime, then for every (t, r) ∈ SpanningTrees • (G) one has

P(LastExitTree(Y k , k ≤ 0) = (t, r)) = Const. e∈E(t,r) ← - M e . (26)
Before proving the Lemma, let us discuss a bit the consequences of the two last lemmas : As discussed in Aldous [START_REF] Aldous | The random walk construction of uniform spanning trees and uniform labelled trees[END_REF] and Broder [START_REF] Broder | Generating random spanning trees[END_REF], when ← -M = M (reversible case) and r fixed, Proof. Equation (26) comes from the fact that one can view the sequence (LastExitTree(Y k , k ≤ m), m ≥ 0) as a Markov chain with state space SpanningTrees • (G) running from -∞2 and therefore under its stationary regime. The kernel Q((t, r), (t , r )) of this chain provides the probability to

  u) where t(u) is the target of the edge starting at u; Weight(C) := (-1) N (C) c cycles of C e∈c M e -,e + the product of the weight of edges along the directed cycles of C, where N (C) the number of cycles of C and finally define Weight(B, C) := Weight(B)Weight(C).

  since W is a Markov chain with kernel M , we need also to consider reverse paths in the proof. For a path w = (w 0 , • • • , w m ) on G denote by |w| = m its number of steps, w = w m its last position, and w = w 0 its first position. Denote by ←w = (w m , w m-1 , • • • , w 0 ) the reverse time path and set

Lemma 7 .

 7 The map Heap : Paths(r) -→ HeapCol w -→ Heap(w) is a weight preserving injection (meaning that Weight(w) = Weight(Heap(w)).

  , • ... the time |w (k) | is the hitting time of HoleSet \ {Final(1), • • • , Final(k -1)} by w (k) , for each k. Remark 14. GolfSequence HoleSet, S is empty if Nb > |HoleSet|, and non-empty if Nb ≤ |HoleSet|.

  Y 0 in (Y -k , Y -k+1 , Y -k+2 , • • • , Y 0 ). Requiring (23) for Markov chains can be done in two natural ways: Lemma 23. (a) If (X k , k ∈ Z) and (Y k , k ∈ Z) are two Markov chains with respective positive Markov kernels M and ← -M on G, with invariant distribution ρ. Assume that both (X k , k ∈ Z) and (Y k , k ∈ Z) are taken under their invariant distributions, then

L

  ((X 0 , • • • , X τm ) | X 0 = r) = L((Y 0 , • • • , Y -Lm ) | Y 0 = r)so that by Lemma 22,P(FirstEntranceTree(X i , 0 ≤ i ≤ τ |V | ) = (t, r) | X 0 = r) = P(LastExitTree(Y ≤0 ) = (t, r)|Y 0 = r) = Const.1 x 0 =r e∈E(t,r)M e /ρ(r).If we do not assume← -M = M , then for X a Markov chain with kernel M , starting under its invariant distribution, we haveP(FirstEntranceTree(X i , 0 ≤ i ≤ τ |V | ) = (t, r)) = P(LastExitTree(Y ≤0 ) = (t, r)) = Const. e∈E(t,r) ← -M e ,and conditional on X 0 = r in the left hand side and Y 0 = r in the right hand side, it gives Theorem 3.

  Let us prove that there exists a path w ∈ Paths(t, r, f ) such that Heap(w) = H. As explained in the proof of Lemma 7, the collection of heaps H can be used to construct a path: denote by p the current point and ←w the current path which are initialized as p = f and ←w = (f ). (a) If H p is empty then stop the construction and "return ←w ". If H p is not empty, consider the last edge (p, u) of the heap H p . (b) Remove (p, u) from H p , add (p, u) as last step in ←w . (c) Set p = u and go to (a).

r, f ) and consider H := H t ⊕ h the potential unique collection of heaps such that Heap Trunc [H] = h.

To conclude here, another argument is needed: the fact that the support of FirstEntranceTree(W0, • • • , Wτ |V | ) is the set of all spanning trees, which is easy to see

When the chain is not aperiodic, it has to be seen as the limit when m → +∞ of a Markov chain starting at -m under its invariant distribution

Acknowledgments

The first author acknowledge support from ERC 740943 GeoBrown.

Acknowledgments

We thank the anonymous referee for her/his corrections and comments.

Conclusion: proof of Theorem 3

From Proposition 18 and Lemma 11, one identifies that Weight(Ξ(t, r, f )) = Weight HeapGolfSequence HoleSet, S, free f Weight(HCycles(free f ))

where HoleSet = ∂t and S is any starting sequence with counting sequence (Nb u , u ∈ V ) = ((Deg in (t,r) (u)-1)1 u∈t o , u ∈ V ): in words Deg in (t,r) (u) -1 balls start at the internal node u. Such a starting sequence (S i , 1 ≤ i ≤ Nb) is easy to build: take any order on t o , and sort the nodes u 1 , • • • , u |t o | , and take as sequence S: the node u 1 repeated Deg in (t,r) (u 1 ) -1 times, followed by u 2 repeated Deg in (t,r) (u 2 ) -1 times, etc. Recall Corollary (12). We want to prove that

.

Taking into account that ρ f = det(Id -M (f ) )

x det(Id -M (x) ) and ( 14) we just need to prove that

but this is precisely what says the trivial stochastic golf sequence property (Proposition 15(ii)).

Remark 19. In Section 2.3 we said that we would use the collection of heaps Heap Trunc (w) while forgetting the initial order of edges coming from w or ←w : we used these collections of heap to define the golf sequences, and the additional heap of cycles, and none of them have been defined using the order of the original steps of w or ←w . However, using portions of w (or ←w ) to define golf trajectories seem possible but brings many complications: because somehow, "the next ball" to be played depends on the arrival position of the previous. In terms of heaps of cycles everything become messy; for example the global heap of cycles produced finally in our construction, needs to be partially piled after each golf path, if one wants to use the chunks of consecutive steps of ←w in their initial order. These considerations make this ensemble quite difficult to follow and would produce a much longer and involved argument.

Remark 20. In the proof, we have rearranged the steps of the random walk with kernel ← -M . What we did -notably around the notion of golf sequences -is reminiscent of Diaconis & Fulton paper [START_REF] Diaconis | A growth model, a game, an algebra, Lagrange inversion, and characteristic classes[END_REF] and the commutative property they proved (this property being also at the core of the study of internal DLA). When one studies a sequence of stopped random paths, where the stopping time of each path depends on the ending points of the preceding paths (the starting points being fixed, and possibly different), under some various conditions, the distribution of the set of final points of the trajectories is independent from the order of the sequence of paths and the distribution of the vector giving the total number of traversals of each edge by the sequence of paths, is also independent from the order of sequence of path.

Proof of Theorem by adaptation of the classical argument

The proof follows mainly, Aldous-Broder's ideas, except that M = ← -M is not an hypothesis; we proceed here and there to some small changes with respect to classical arguments.

The LastExitTree. Any path (z 0 , • • • , z n ) on G can be used to define a rooted tree

rooted at z n , as follows: set (Γ 0 , z 0 ) as the tree reduced to its root z 0 ; from k = 0 to n -1, construct (Γ k+1 , z k+1 ) from (Γ k , z k ) by the addition of the edge (z k , z k+1 ) and the suppression of the outgoing edge from z k+1 (if any). The set of nodes of (

the last time k nodes are to be visited "in the future", which is also a last visit time for a node. It follows that the tree LastExitTree(z 0 , • • • , z n ) has root z n and has for edges

In Definition 1, we defined the FirstEntranceTree associated with a covering path; this definition can be extended to any path, covering or not, killed at the covering time or not. The following lemma is proved by a straightforward checking: Lemma 21. For any path (w 0 , . . . , w n ) on G:

Several remarks follow:

non decreasing, and the jumps of this sequence correspond to the τ m = inf{j : |{w 0 , • • • , w j }| = m} where a new node is attached to the tree. Moreover, for a Markov chain (W i , i ≥ 0),

• The right hand side in (22) is somehow not natural since we reverse the time (time is decreasing). The following Lemma is a direct consequence of the previous one Lemma 22. Assume that (X k , k ≥ 0) and (Y k , k ≤ 0) are two processes such that,

For

we have

and then

pass from (t, r) to (t , r ); this weight is ← -M r,r or 0 depending on whether the root displacement is enough to transform t into t or not (together with the removal of the outgoing edge from r in t). The trees (t, r) which may lead to (t , r ) do not have the (oriented) edge (r, r ) but an edge from r to one of the neighbors u of r in G; this is the only difference between t and t . The trees (t, r) having (t , r ) as neighbour (see Fig . 4) are then parameterized by these neighbours u of r , and the balance equation (if one assumes P (t, r) = e∈E(t,r)

← -M e ), As mentioned by Aldous [START_REF] Aldous | The random walk construction of uniform spanning trees and uniform labelled trees[END_REF], the irreducibility follows the fact that the LastExitTree of the sequence of steps that forms the depth first traversal of a tree is the tree itself. Remark 25. In Hu & al. [START_REF] Hu | A reverse Aldous-Broder algorithm[END_REF], it is established that the first entrance tree and the last exit tree taken at the cover time of the Markov chain, have same distribution.


est destinée au dépôt

22

)

)

)2 0) 02 2) 22 )) )2 ) 2) 2) )) 2) ) 2 2

  Outcrossing via the Buller phenomenon in a substrate simultaneously inoculated with spore and mycelium of Agaricus bisporus creates variability for agronomic traits. Philippe Callac, Micheline Imbernon, Jean-Michel Savoie To cite this version: Philippe Callac, Micheline Imbernon, Jean-Michel Savoie. Outcrossing via the Buller phenomenon in a substrate simultaneously inoculated with spore and mycelium of Agaricus bisporus creates variability for agronomic traits.. 6. International Conference on Mushroom Biology and Mushroom Products, World Society for Mushroom Biology and Mushroom Product, Sep 2008, Bonn, Germany. hal-