Charles Bordenave

Bastien Dubail

Markovian linearization of random walks on groups

come

Introduction

Let A be a complex unital algebra and consider a non-commutative polynomial P = P(x 1 , . . . , x n ) in the variables x 1 , . . . , x n ∈ A. In many cases, a detailed study of the relevant properties of P is possible only when the degree of P is small, typically when P is of degree one, in which case P is just a linear combination of the x i 's. The linearization trick precisely consists in constructing another polynomial P of degree one, which can be related to the relevant properties of P. It thus can be used to make computations that were not a priori possible for P. The price to pay is an enlargement of the algebra: writing P as a finite sum of monomials

P = i 1 ,...,i k α i 1 ...i k x i 1 ⋯ x i k ,
with α i 1 ...i k ∈ C, P is generally constructed as

P = i αi ⊗ x i
where αi ∈ M r (C) are complex matrices. Therefore P is no longer in the algebra A but in the algebra M r (C) ⊗ A for some integer r that depends on P (usually through its degree).

Under various names, the linearization trick has been used in several domains such as electrical engineering, random matrices, operators algebras, automata theory, etc, we refer to the survey [13]. A famous application of the linearization trick in operator algebra is the computation of the spectrum of a non-commutative polynomial. If a ∈ A, the spectrum of a is defined as σ(a) ∶= {z ∈ C, zIa is not invertible}. Given a non-commutative polynomial P(x 1 , . . . , x n ) ∈ A, it is possible to construct a linear P ∈ M r (C) ⊗ A for some integer r, such that (zI -P) is invertible in A if and only if (Λ(z)⊗I A -P) is invertible in M r (C)⊗A, where Λ(z) is the r × r matrix with only zero elements except the (1, 1) entry which is z. Moreover, (zI -P) -1 is then precisely the (1, 1) entry of (Λ(z) ⊗ I A -P) -1 (seen as a r × r matrix of elements in A). Such a construction can be found for instance in the monograph [START_REF] James | Free probability and random matrices[END_REF]Chapter 10].

As illustrated in this last example, we note that the relevant properties of P (here its spectrum and its resolvent) dictates the linearization procedure. In this paper, we introduce a new linearization of the Markov kernel of a random walk with finite range on a group. This linearization is a new Markov kernel on an enlarged state space and it corresponds to a nearest-neighbor random walk on the group. Classical quantities such as speed or entropy rate of the original random walk can be read on the new random walk. We illustrate our method on free groups and free product of finite groups. Notably, we establish new formulas for drift and entropy of finite range random walks on these groups.

The linearization trick and colored random walks on groups

We let G be a finitely generated group with identity element e and we fix a finite set of generators S. We assume that S is symmetric, meaning that g ∈ S implies g -1 ∈ S. Let p = (p g ) g∈G be a probability measure on G. Consider the Markov chain (X n ) n≥0 on G with transition probabilities

P[X n = h X n-1 = g] = p g -1 h
, for all g, h ∈ G. Such a Markov chain is called a convolution random walk.

The random walk is said to be finitely supported, or to have finite range, if the measure p is finitely supported. It is a nearest-neighbor random walk if p is supported on the set of generators S.

As for any Markov chain, the transition kernel of a right convolutional random walk can be seen as an operator acting on square integrable functions: f = f (x) ↦ (Pf )(x) = ∑ y P (x, y)f (y). In the present case, it can be written in terms of the left multiplication operators λ(g), g ∈ G, defined as: for all f ∈ 2 (G), λ(g) ⋅ f ∶ x ↦ f (gx).

Letting P(g, h) = p g -1 h it is then possible to write P = g∈G p g λ(g).

(

) 1
This sum is finite if and only if the random walk is finitely supported. Furthermore, λ is a group morphism so λ(gh) = λ(g)λ(h) for all g, h ∈ G (λ is the left regular representation).

Writing each element g in the support of the walk as a product of elements of S, it is thus possible to write P as a non-commutative polynomial in the operators λ(g), g ∈ S. In other words, P is an element of the left group algebra which is generated by the λ(g)'s, g ∈ G.

The polynomial P is of degree 1 if and only if the random walk is nearest neighbor. With this point of view, the linearization trick potentially allows to study any finitely supported random walk by considering instead a "nearest-neighbor operator"

P = g∈G pg ⊗ λ(g) (2)
for some well-chosen matrices pg ∈ M r (C) such that ∑ g pg is a stochastic matrix, that is, the transition kernel of a Markov chain on [r] where for n ≥ 1 integer, we set [n] = {1, . . . , n}.

Then, it turns out that this operator P is the transition kernel of a Markov chain ( Xn ) n on the state space G × [r], which at each step moves from a pair (g, u) to a pair (h, v) with probability pg -1 h (u, v). Equivalently, if one interprets [r] as a set of colors, Xn can at each step be multiplied by g ∈ G while the color is updated from u to v with probability p g (u, v). Such a Markov chain will be called a colored random walk and can thus be defined similarly to a classical convolution random walk.

Definition 1. Let p = (p g ) g∈G be a family of matrices with non-negative coefficients of M r (R) such that

P = g∈G p g (3)
is a stochastic matrix. A colored random walk is a Markov chain (Y n ) n on the state space G × [r], with transition probabilities

P[Y n = (h, v) Y n-1 = (g, u)] = p g -1 h (u, v).
The support of the random walk is the set of elements g ∈ G such that p g ≠ 0. The colored walk is finitely supported if the support is finite, nearest-neighbor if the support is included in S.

By looking only at the color coordinate, (Y n ) induces a Markov chain on the set of colors [r] whose transition matrix is exactly the matrix P in [START_REF] Bougerol | Products of random matrices with applications to Schrödinger operators[END_REF].

Irreducibility assumptions. For standard convolution random walks, it is generally assumed that the support generates the whole group, which then makes the random walk irreducible. For colored random walks, we will make the same assumption but suppose as well that the matrix P defines an irreducible Markov chain on the colors. Note this assumption does not necessarily make the colored walk irreducible, for there may be unreachable pairs (g, u). Definition 2. A colored walk is quasi-irreducible if the marginal of its support on G generates the whole group and the matrix P is irreducible.

Reversibility. An important property satisfied by some Markov chains is reversibility. Recall that, if X is a countable set, ν a measure on X and Q is a Markov chain, then Q is said to be reversible with respect to ν if for all x, y ∈ X, ν(x)Q(x, y) = ν(y)Q(y, x). In other words, Q seen as an operator on 2 (X, ν) is self-adjoint. In our setting, P defined in ( 1) is said to be reversible if it is reversible for the counting measure on G. This is equivalent to the condition: for all g ∈ G, p g = p g -1 . Similarly, consider a colored random walk P of the form (2). Assume that P defined by (3) has invariant measure π on [r]. Then P is reversible if it is reversible for the product of π and the counting measure on G. This is equivalent to the condition, for all g ∈ G, u, v ∈ [r],

π(u)p g (u, v) = π(v)p g -1 (v, u).

Main results

Linearizing random walks. The main contribution of this paper is to formalize a way to apply the linearization trick to random walks on groups. Definition 3. Let G be a a group generated by a finite set S, with identity element e. Let (X n ) n≥0 be a random walk with kernel P as in (1) and with finite support generating G. Let (Y n ) n≥0 on G × [r] be a quasi-irreducible, nearest-neighbor colored random walk with kernel P as in (2). We say that (Y n ) n≥0 linearizes (X n ) n≥0 (or P linearizes P) if the following two property holds: (i) if Y 0 = (e, 1) there exists a sequence of stopping times (τ n ) n≥0 with τ 0 = 0 such that (Y τn ) n≥0 is a realization of the random walk (X n ) n≥0 with initial condition e, and (ii) these stopping times are a renewal process, that is the variables τ n+1 -τ n are iid with finite mean.

To be precise, in the above definition, when saying that Y τn is a convolution random walk, we of course identify Y τn with its G coordinate and forget about the color, which in this case is constant equal to 1.

We remark also that because of a transitivity property, namely one can always translate the starting point to e ∈ G by left multiplication, there is no loss of generality in supposing that the walks are started at e ∈ G. More details on this are given in Section 3.

Theorem 1. Let G be a a group generated by a finite set S, with identity element e. Consider a random walk with kernel P as in [START_REF] Blachère | Asymptotic entropy and Green speed for random walks on countable groups[END_REF] with finite support generating G. Then there exists r ≥ 1 and a colored random walk on G × [r] with kernel P as in (2) which linearizes P. Moreover, if P is reversible, then P can be chosen to be also reversible.

Theorem 1 has been stated in a non-constructive manner for ease of notation. The proof of Theorem 1 in Section 2 will exhibit two simple linearization constructions which have a vector p = (p g ) g∈G as input and gives as output the integer r and the family of matrices (p g ) g∈S . There is one construction in the general case and one construction which preserves reversibility. We refer to Remark 4 for the number of colors r needed in both constructions. We note also that the previous spectral linearization tricks reviewed in [13] did not preserve the Markov property and could not be used to prove Theorem 1.

There are possible extensions of the Markovian linearization trick. It is possible with the same proof techniques to linearize a colored random walk on G × [r] with finite range and obtain a colored nearest-neighbor colored random walk on G × [r ′ ] with r ′ ≥ r. In another direction, it is possible to linearize random walks on G which do not have a finite range provided that we allow a countable set of colors, see Remark 2 below. Finally, in this paper we focus on groups only but our first linearization construction applies to random walks on monoids as well.

Application to the computation of drift and entropy. Initially, our goal was to use the linearization trick to try to compute explicit formulas for various invariant quantities of interest, mainly entropy and drift.

Elements of G can be written as products of elements in S, which will be called words. A word a 1 ⋯a k with the a i ∈ S such that g = a 1 ⋯a k is called a representative of the element

g ∈ G. The length with respect to S of g ∈ G is g ∶= min{k, g = a 1 ⋯a k , a i ∈ S}. ( 4
)
Consider a convolution random walk (X n ) n≥0 on a finitely generated group G, started at e. Assuming finite moment E [ X 1 ] < ∞, which is always satisfied if the walk is finitely supported, the sequence (E [ X n ]) n≥0 is easily shown to be sub-additive (see Section 3), which implies the existence of the limit

γ ∶= lim n→∞ E X n n .
The scalar γ is called the drift, or rate of escape, of the random walk. The drift γ is in fact also an a.s. and L 1 limit, as can be shown using for instance Kingman's sub-additive theorem. Therefore

γ ∶= lim n→∞ X n n a.s. and in L 1 .
Similarly, from the definition of the entropy of X n as

H(X n ) ∶= - g P [X n = g] log P [X n = g] one can define h ∶= lim n→∞ H(X n ) n .
as an L 1 limit or as an a.s. limit:

h = lim n→∞ - log P n (e, X n ) n a.s.

and in L 1

where P n the n-th power of the transition kernel of the random walk. h is called the Avez entropy, or entropy rate, or asymptotic entropy, of the random walk. In fact, this entropy can be interpreted as the drift for the Green pseudo-metric, see [START_REF] Blachère | Asymptotic entropy and Green speed for random walks on countable groups[END_REF]. In this paper it will often simply be referred to as the entropy of the random walk. We refer the reader to Woess [START_REF] Vadim | Random walks on discrete groups: boundary and entropy[END_REF] for a general reference on the topic. These notions can be extended to colored random walks: it is straightforward to extend the definition of H(X n ), while for the drift we set x ∶= g for all x = (g, u) ∈ G × [r].

Proposition 2. Let (X n ) n≥0 be a quasi-irreducible colored random walk on a group G. The following limits exist and do not depend on the starting color:

γ = lim n→∞ X n n a.s. and in L 1 , (5)
h = lim n→∞ - log P n ((e, u), X n ) n a.s. and in L 1 . (6)
for all starting color u ∈ [r].

The proof is given to Section 3. The a.s. convergence of the entropy and drift combined with the law of large numbers yield the following corollary. Corollary 3. Let (X n ) n≥0 be a finitely supported random walk on a group G and (Y n ) n≥0 a colored random walk that linearizes (X n ) n≥0 in the sense of Definition 3. The drift γ and entropy h of (Y n ) n≥0 can be related to the drift γ and entropy h of (X n ) n≥0 by:

γ = E[τ 1 ]γ, (7)
h = E[τ 1 ] h. (8)
The expected time E[τ 1 ] has a simple expression in the two linearization constructions given in Section 2, see Remark 1 and Remark 3.

In this paper, we have chosen to focus on drift and entropy but there are other numerical invariants associated to a random walk such as the spectral radius of P or the index of exponential decay of the return probability: lim n→∞ P 2n (e, e) 1 (2n) (they coincide for reversible walks). Our linearization technique could also be used to study these last two quantities but this is less novel since these quantities can be read on the resolvent operator and previous linearization techniques allow to compute resolvent of operators of the form (1), see [13] for such linearization and [START_REF] Lehner | Computing norms of free operators with matrix coefficients[END_REF]6] for examples of computation of resolvent operators of the form (2).

Entropy and drift for plain groups. Most of the time the exact computation of the drift and entropy is not accessible. However for nearest-neighbor random walks on groups with an underlying tree structure like free groups [START_REF] Vadim | Random walks on discrete groups: boundary and entropy[END_REF][START_REF] Ledrappier | Some asymptotic properties of random walks on free groups[END_REF] and free products of finite groups [START_REF] Jean | Random walks on groups and monoids with a Markovian harmonic measure[END_REF][START_REF] Mairesse | Random walks on free products of cyclic groups[END_REF][START_REF] Lorenz | Rate of escape of random walks on free products[END_REF]7], there exist techniques that yield explicit formulas. This paper shows how to extend extend some of these techniques to the colored setting. Combined with the linearization trick, our results give explicit formulas for finitely supported random walks. By 'explicit', we mean that we express drift and entropy in terms of the unique solutions of some finite dimensional fixed point equations.

Following [START_REF] Jean | Random walks on groups and monoids with a Markovian harmonic measure[END_REF], we combine the case of free groups and free product of finite groups. These groups are called plain groups in [START_REF] Jean | Random walks on groups and monoids with a Markovian harmonic measure[END_REF][START_REF] Robert | Groups and simple languages[END_REF]. Definition 4. A plain group is a free product of a finitely generated free group and a finite family of finite groups.

Write F d for the free group on d generators a 1 , . . . a d and let G 1 , . . . , G m be finite groups.

Consider the plain group

G = F d * G 1 * ⋯ * G m , with the set of generators S ∶= d ⋃ i=1 {a i , a -1 i } ⋃ ⎛ ⎝ m ⊔ j=1 S j ⎞ ⎠ .
In the above expression, for all j = 1, . . . , m, S j ∶= G j ∖ {e} is the set of elements of G j distinct from the identity element, and ⊔ denotes a disjoint union. Introducing the notation from [START_REF] Jean | Random walks on groups and monoids with a Markovian harmonic measure[END_REF],

∀g ∈ S, Next(g) ∶= ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ S ∖ {g -1 } if g ∈ F d S ∖ S i if g ∈ S i , (9)
we see that every element g ∈ G writes as a word g = g 1 ⋯g n with n = g and g i+1 ∈ Next(g i ) for all i = 1, . . . , n -1.

If we set aside the trivial cases where G is isomorphic to Z or Z 2Z * Z 2Z, G is a nonamenable group which implies any irreducible convolution random walk on G is transient (see for instance [START_REF] Woess | Random walks on infinite graphs and groups[END_REF]Chapter 1]). Therefore if X n is a convolution random walk on G, X n → ∞ and X n converges in some sense to an infinite word X ∞ made of letters in S. The law p ∞ of X ∞ is called the harmonic measure and it provides much information on the asymptotic properties of X n . It can in particular be used to compute its entropy and drift. Given g ∈ S, let µ g ∶= p ∞ [ξ 1 = g] be the probability under p ∞ that an infinite word starts with letter g. The most explicit formulas for nearest-neighbor random walks on plain groups express the entropy and drift in terms of the parameters p g and µ g .

In this paper we extend this technique to the colored setting. It had already been shown that such techniques could be adapted to nearest-neigbhor random walks on more general free products, see notably [START_REF] Nagnibeda | Random walks on trees with finitely many cone types[END_REF][START_REF] Lorenz | Rate of escape of random walks on free products[END_REF][START_REF] Lorenz | Asymptotic entropy of random walks on free products[END_REF]. Here, the non-commutativity of M r (C) creates new difficulties. We consider a natural generalization of the harmonic measure p ∞ u , u ∈ [r] being the starting color, and a matrix version of the parameters µ g , which satisfy

p ∞ u (ξ 1 = g) = v∈[r] µ g (u, v), ∀u ∈ [r].
The family of parameters (µ g ) g∈S is uniquely characterized by a family of matrix relations [START_REF] James | Free probability and random matrices[END_REF], called the traffic equations, which arrives as consequences of the stationarity. The traffic equations can be solved quite explicitly for the free group. The precise definitions and properties of the harmonic measure are given in Section 4.

We start with a formula for the drift. In the sequel, 1 denotes the vector R r with all coordinates equal to 1 and 1 u the indicator at u ∈ [r], that is the vector with zero coordinates except the u entry equal to 1. The usual scalar product is denoted by ⟨ , ⟩. Theorem 4. Let (Y n ) n≥0 be a nearest-neighbor quasi-irreducible colored random walk on G × [r] defined by a family of matrices (p g ) g∈S . Let π be the unique invariant probability measure of the stochastic matrix P = ∑ g p g . The drift of (Y n ) n≥0 is given by

γ = g∈S ⟨1, πp g -µ g -1 + h∈Next(g) µ h ⟩. = g∈S u,v,w∈[r] π(u)p g (u, v) -µ g -1 (v, w) + h∈Next(g) µ h (v, w) .
Theorem 4 is the exact counterpart of the already known formulas for colorless walks (corresponding to r = 1).

For the entropy, we first provide an integral formula in Theorem 5 which is again the counterpart of a known formula in the colorless setting.

Theorem 5. Let (Y n ) n≥0 be a nearest-neighbor quasi-irreducible colored random walk on G × [r] defined by a family of matrices (p g ) g∈S . Let π be the unique invariant probability measure of the stochastic matrix P = ∑ g p g . The asymptotic entropy of (Y n ) n≥0 is given by

h = - g∈G u,v∈[r] π(u)p g (u, v) log dg -1 p ∞ u dp ∞ v dp ∞ v . (10)
For nearest-neighbor convolution random walks on plain groups, it is then possible to derive an explicit expression from this integral formula. For colored random walks, adapting the computation naturally leads to the problem of determining the limit of infinite products of random matrices, which in turn leads to a formula of the entropy in terms of the parameters (µ g ) g∈S and the law of a family indexed by [r] of random probability measures on R r whose law is uniquely characterized by some invariance equation.

To state our result more precisely, we first introduce the hitting probabilities defined as follows. Given g ∈ G, u ∈ [r], let τ (g,u) ∶= inf{n ∶ X n = (g, u)} be the hitting time of a pair (g, u), so that τ g ∶= min u τ (g,u) is the hitting time of g. For g ∈ S, set

q g (u, v) ∶= P[τ g < ∞ and τ g = τ (g,v) ]. (11)
As we will check, the matrices q g and µ g satisfy a simple relation (28) and the hitting probabilities (q g ) g∈S are characterized by a quadratic equation ( 27) which can be solved quite explicitly for the free group. In the statement below, P + denotes the open simplex of probability measures [r]:

P + ∶= ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ x ∈ R r ∶ i∈[r]
x i = 1 and

x i > 0, ∀i ∈ [r] ⎫ ⎪ ⎪ ⎬ ⎪ ⎪ ⎭ . ( 12
)
Theorem 6. Suppose the matrices (q g ) g∈S satisfy (43) defined in Section 3. Then the entropy of the colored random walk is given by

h = - g∈S u,v,w∈[r] π(u)p g (u, v) ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ µ g -1 (v, w) log ⎛ ⎝ ⟨1 v , z⟩ ⟨q g -1 (u, ⋅) , z⟩ ⎞ ⎠ dν w (z) + h∈Next(g) µ h (v, w) log ⟨q g (v, ⋅) , q h z⟩ ⟨1 u , q h z⟩ dν w (z) + h∈S∶gh∈S µ h (v, w) log ⎛ ⎝ ⟨q gh (v, ⋅) , z⟩ ⟨q h (u, ⋅) , z⟩ ⎞ ⎠ dν w (z) ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ , (13)
where (ν u ) u∈[r] is the unique family of probability measures on P + satisfying

f (z) dν u (z) = g∈S v∈[r] f (q g z)µ g (u, v) dν v (z), ∀u ∈ [r],
for all bounded measurable functions f on P + . The technical condition (43) is described in Section 3. Let us simply note that this condition is automatically satisfied for colored random walks arising as a linearization of a finite range random walk on G (this is the content of Proposition 17 below). Applying Theorem 6 to a nearest-neighbor walk for which r = 1, π = 1, ν = δ 1 , we get back formula [START_REF] James | Free probability and random matrices[END_REF] in [START_REF] Jean | Random walks on groups and monoids with a Markovian harmonic measure[END_REF]:

h = - g∈S p g ⎛ ⎝ µ g -1 log 1 q g -1 + h∈Next(g) µ h log q g + h∈S∶ gh∈S µ h log q gh q h ⎞ ⎠ .
As alluded to above, in Theorem 6, the measure ν g on P + will arise as the convergence in direction toward a random rank one projector of the product of matrices q g 1 q g 2 ⋯q gn where g 1 , g 2 , . . . in S are the successive letters of X ∞ with law p ∞ conditioned to start with g 1 = g.

For finite range random walks on plain groups, fine qualitative results on drift and entropy were already available such as [START_REF] Steven P Lalley | Finite range random walk on free groups and homogeneous trees[END_REF][START_REF] Ledrappier | Analyticity of the entropy for some random walks[END_REF] and even on general hyperbolic groups [11,[START_REF] Gilch | Regularity of the drift and entropy of random walks on groups[END_REF] and references therein. As pointed in [START_REF] Ledrappier | Some asymptotic properties of random walks on free groups[END_REF][START_REF] Gilch | Regularity of the drift and entropy of random walks on groups[END_REF], the computations for drift and entropy for nearest-neighbor random walk on the free group have been known for around 50 years but it was however unexpected that these explicit formulas could be extended to finite range random walks. To our knowledge, Theorem 4 and Theorem 6 provide the first formulas for finite range random walks on plain groups, see Figure 1 for a numerical illustration.

Organization of the paper. In Section 2 we propose a general construction of linearized colored walks, with some variations, that lead to Theorem 1. Section 3 is devoted to the proof of Proposition 2. In Section 4 we define the harmonic measure for a random walk on a plain group. Mimicking results for standard random walks, we prove the Markovian structure of the harmonic measure, which is the main ingredient for computing drift and entropy. The computations leading to Theorem 4 and Theorem 5 and additionnal formulas for the entropy are given in section 5. Finally Section 6 provides a modest example illustrating the use of the linearization trick.

Acknowledgments. Part of this work was performed during a visit of both authors to Kyoto University. Both authors gratefully acknowledge the support of JSPS and Kyoto University. CB was supported by the research grant ANR-16-CE40-0024-01.

2 Linearization: proof of Theorem 1

Let (X n ) n≥0 be a finitely supported random walk on G. In this section we construct a nearest-neighbor colored random walk (Y n ) n≥0 from (X n ) n≥0 in such a way the entropy and drift can easily be related. What seems the most natural is to directly look for Y n as the walk that follows the same trajectory as X n but decomposes a transition in several steps in order to be nearest-neighbor. What follows formalizes this idea and adds two possible improvements. The first improvement allows to reduce the dimension of the matrices, the second is a linearization that preserves reversibility.

From now on, let a 1 , . . . , a d be the elements of the generating set S, and a 0 ∶= e. Let K denote the support of the probability measure p and K be the maximal length of an element of K. For each g ∈ K choose a representative s(g), which can always be assumed to be of length g . We will generally identify g with its representative and write simply

g = a i 1 ⋯a i k to refer to the fact that s(g) = a i 1 ⋯a i k , for some i 1 , . . . , i k ∈ [d].
Similarly, set p i 1 ⋯i k ∶= p g , with in particular p 0 ∶= p e and p i ∶= p a i , whether a i ∈ K or not. Since we look for a nearest-neighbor colored random walk, the colored random walk

(Y n ) n≥0 is defined by the r × r matrices pi , i ∈ [0 ∶ d].
Initial construction. As mentioned previously, one can first construct Y n as the walk which, when X n is multiplied by g = a i 1 ⋯A i k ∈ K, visits each a i consecutively. Colors can be used to impose Y n to follow the trajectory of the initial random walk X n . For instance, consider a neutral color, written 1 and given

g = a i 1 ⋯a i k ∈ K, consider k -1 different colors u 1 (g), . . . , u k-1 (g) and set pi 1 (1, u 1 (g)) ∶= p g , pi 2 (u 1 (g), u 2 (g)) ∶= 1, . . . , pi k (u k (g), 1) = 1.
Here the color 1 is to be interpreted as a neutral color: supposing the colored walk Y n is at (e, 1), it goes to a i 1 with probability p i 1 ⋯i k , and is then forced to go through a i 2 ⋯a i k until it is back at color 1. Except for the color 1, all the colors serve only for the intermediary steps. If one considers now another element h ∈ K, h = a i ′ 1 ⋯a i ′ k ′ , one can take k ′ -1 new colors to distinguish between the intermediary steps which lead to g and those which lead to h. Repeating the process with each generator in the support of the walk, one can construct a colored random walk

(Y n ) n≥0 such that Y τn (d)
= X n for all n, where τ n are the successive hitting times of the color 1.

Linearization in the non-reversible case

We now describe more precisely a construction which reduces the number of colors needed in the initial construction by noticing that elements with common prefixes can use the same colors when visiting these prefixes.

Recall that a representative of minimal length has been fixed for each element of K. These representatives are called the representatives of

K. Given g, h ∈ K, g = a i 1 ⋯a i k , h = a j 1 ⋯a j k ′ , the prefix of g and h is defined as g ∧ h = a i 1 ⋯a im where m ∶= max{n ≥ 0 ∶ i 1 = j 1 , . . . , i n = j n }. h is a strict prefix of g if g ∧ h = h and g > h . For k ∈ [ K ] and i 1 . . . , i k ∈ [d], let [i 1 ⋯i k ] ∶= {g ∈ K, g ∧ a i 1 ⋯a i k = a i 1 ⋯a i k , g ≥ k + 1} and p [i 1 ⋯i k ] ∶= g∈[i 1 ⋯i k ]
p g be the cumulative mass under p of all words in K for which a i 1 ⋯a i k is a strict prefix. Then for k ∈ [ K ], we set

q i 1 ⋯i k = p [i 1 ⋯i k ] p [i 1 ⋯i k-1 ]
where the denumerator is to be taken as equal to one in the case k = 1.

Here we will make use of the operator point of view in order to write all the matrices defining (Y n ) n≥0 at once. As M r (C) ⊗ A is isomorphic to M r (A) for any unital algebra A, the transition kernel P can be written as one matrix whose coefficients are operators on 2 (G). In this case, the matrix has coefficients which are linear combinations of the multiplication operators. The matrices p i , i ∈ [0, d] can easily be deduced: to obtain p i it suffices to replace λ(a i ) by 1 and the λ(a j ), j ≠ i by 0.

For all k ∈ [ K ], let

r k ∶= Card {(i 1 , . . . , i k ) ∈ S k , [i 1 ⋯i k ] ≠ ∅}
be the number of strict prefixes of elements of K that have length k. Then, we define the following matrices:

C(k) is the r k-1 × 1 column matrix C(k) ∶= ⎛ ⎝ j∈[d] p i 1 ⋯i k-1 j p [i 1 ⋯i k-1 ] λ(a j ) ⎞ ⎠ i 1 ⋯i k-1
, which is indexed by strict prefixes of K of length k -1. Given a representative i 1 ⋯i k-1 , define the row matrix

L(i 1 , . . . , i k-1 ) ∶= (q i 1 ⋯i k-1 j λ(a j )) j
indexed by all j such that i 1 ⋯i k-1 j is the strict prefix of a representative of K. Then use these row matrices to form the

r k-1 × r k diagonal block matrix D(k), whose i 1 ⋯i k-1 diagonal entry is L(i 1 , ⋯, i k-1 ): D(k) = ⎛ ⎜ ⎜ ⎝ ⋱ L(i 1 , . . . , i k-1 ) ⋱ ⎞ ⎟ ⎟ ⎠ .
Finally combine all the preceding matrices to construct:

P ∶= ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ∑ i∈[0∶d] p i λ(a i ) D(1) 0 0 C(2) 0 D(2) C(3) 0 0 D(3) ⋮ ⋱ C( K -1) D( K -1) C( K ) 0 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ (14)
Example 1. The construction will certainly be clearer on a concrete example. Consider a random walk on the group G given by the presentation ⟨a, b ab = ba⟩, which is in fact isomorphic to Z 2 . Suppose the random walk is supported by all words in a and b of length less than 3, that is

K = {e, a, b, a 2 , ab, b 2 , a 3 , a 2 b, ab 2 , b 3 }.
To avoid large matrices, we forget about the inverses a -1 , b -1 but they should not be discarded in a general case. Because of the relation ab = ba, there can be several ways to write an element of G as words in a and b, for instance bab = ab 2 . Therefore we fix a representative for each element of the support. In the present case, group elements can be written uniquely as a k b l so it is natural to choice these words as representatives.

Applying the preceding construction, one eventually obtains the following operator matrix:

⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ p e λ(e) + p a λ(a) + p b λ(b) q a λ(a) q b λ(b) 0 0 0 p a 2 p [a] λ(a) + p ab p [a] λ(b) 0 0 q a 2 λ(a) q ab λ(b) 0 p b 2 p [b] λ(b) 0 0 0 0 q b 2 λ(b) p a 3 p [a 2 ] λ(a) + p a 2 b p [a 2 ] λ(b) 0 0 0 0 0 p ab 2 p [ab] λ(b) 0 0 0 0 0 p b 3 p [b 2 ] λ(b) 0 0 0 0 0 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
where

q a = p [a] = p a 2 + p ab + p a 3 + p a 2 b + p ab 2 , q b = p [b] = p b 2 + p b 3 , q a 2 = p [a 2 ] p [a] = (p a 3 + p a 2 b ) p [a] q ab = p [ab] p [a] = p ab 2 p [a] , q b 2 = p [b 2 ] p [b] = p b 3 p [b] .
Proof of Theorem 1 (non-reversible case). On row i 1 ⋯i k , the sum of entries of the matrix

P = ∑ pi is j∈[d] p i 1 ⋯i k-1 j p [i 1 ⋯i k-1 ] + j∈[d] q i 1 ⋯i k-1 j = 1 p [i 1 ⋯i k-1 ] j∈[d] (p i 1 ⋯i k-1 j + p [i 1 ⋯i k-1 j] ) = 1.
Thus P is stochastic and P defines indeed a colored random walk

(Y n ) n≥0 . Suppose now Y n = (g n , u n ) is started at color 1.
Then define (τ n ) n≥0 as the successive return times at the first color: τ 0 ∶= 0 and for n ≥ 1

τ n ∶= inf{m > τ n-1 , u m = 1}
By the Markov property, the random variables τ n -τ n-1 are iid with the same law as τ 1 .

For all g = i 1 ⋯i k in K, the probability that Y τ 1 = g is

P [Y τ 1 = g] = q i 1 q i 1 i 2 ⋯ q i 1 ⋯i k-1 p i 1 ⋯i k p [i 1 ⋯i k-1 ] = p [i 1 ] p [i 1 i 2 ] p [i 1 ] ⋯ p [i 1 ⋯i k-1 ] p [i 1 ⋯i k-2 ] p i 1 ⋯i k p [i 1 ⋯i k-1 ] = p i 1 ⋯i k = p g .
By Markov property and the fact that the increments are iid one easily deduce that

Y τn (d)
= X n for all n ≥ 0. Finally, the irreducibility of X n implies the quasi-irreducibility of Y n .

Remark 1. The expectation of the hitting time τ 1 is very simple to compute: Y 1 can go through each g ∈ K with probability p g , in which case it needs g steps to get back to the color 1. Hence the expectation of τ 1 is just the average length of elements in K:

E [τ 1 ] = p e + g∈K p g g = p e + E[ X 1 ].
(e, 1)

a i 1 u 1 (g) a i 1 a i 2 u 2 (g) a i 1 ⋯a i k-2 u k-2 (g) a i 1 ⋯a i k-1 u k-1 (g) (g, 1) ∈ K × {1} K × {1} α g 1 2 1 2 1 2 1 2 α g Figure 2:
The linearizing reversible random walk Remark 2. If P is not of finite range, then the construction produces a countable set of colors. The construction could nevertheless be useful if the expected time

E[τ 1 ] = p e + E[ X 1 ] is finite.

Linearization in the reversible case

In the previous constructions, it is impossible for the colored random walk to backtrack and hence to be reversible.

To correct this, we propose the following variation of the initial construction. We assume that for all g ∈ K, the representative of g = a i 1 ⋯a in is chosen such that the representative of g -1 is a -1 in ⋯a -1 i 1 . We start with the neutral color 1 and, for each pair (g, g -1 ) with g = g -1 ≥ 2, we add g -1 new colors u 1 (g), . . . , u g -1 (g) and we set u k (g -1 ) = u g -k (g) for all 1 ≤ k ≤ g -1. Suppose g is written as g = a i 1 ⋯a i k . For all h ∈ G, the transition probability to go from (h, 1) to (ha i 1 , u 1 (g)) is set to some value α g to be determined, such that α g = α g -1 and ∑ g∈S α g = 1. All other transition probabilities on the segment joining (x, 1) to (xg, 1) are set to 1 2, see Figure 2.

In matrix form, the construction is as follows. Given α ∈ R + and g = a i 1 ⋯a i k , k ≥ 3, consider the following operator-valued matrix of size k × k

A g (α) ∶= ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 0 αλ(a i 1 ) 0 ⋯ 0 αλ(a -1 i k ) 1 2 λ(a -1 i 1 ) 0 1 2 λ(a i 2 ) 0 ⋯ 0 0 1 2 λ(a -1 i 2 ) 0 ⋱ ⋮ ⋮ 0 ⋱ 0 0 0 ⋮ 1 2 λ(a -1 i k-2 ) 0 1 2 λ(a i k-1 ) 1 2 λ(a i k ) 0 ⋯ 0 1 2 λ(a -1 i k-1 ) 0 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ . If k = 2, let A a i 1 a i 2 (α) ∶= ⎛ ⎝ 0 αλ(a i 1 ) + αλ(a -1 i 2 ) 1 2 λ(a i 2 ) + 1 2 λ(a -1 i 1 ) 0 ⎞ ⎠ . If k = 1, let A a i (α) = (αλ(a i ) + αλ(a -1 i ))
and finally for k = 0 set A e (α) ∶= (αλ(e)). In the case k ≥ 2, one can write

A g (α) = ⎛ ⎝ 0 L i 1 ,i k (α) C i 1 ,i k Ãi 2 ⋯i k-1 ⎞ ⎠
, where L i 1 ,i k (α), C i 1 ,i k are respectively a 1 × (k -1) row matrix and a (k -1) × 1 column matrix, while Ãi 2 ⋯i k-1 is a tri-diagonal (k -1) × (k -1) matrix depending only i 2 , . . . , i k-1 , with zero diagonal. Now given a square matrix M of matrix m × m, use A g (α) to form the matrix of size m + k -1

M ∪ A g (α) ∶= ⎛ ⎜ ⎜ ⎜ ⎝ M L i 1 ,i k (α) 0 C i 1 ,i k 0 Ãi 2 ,...,i k-1 ⎞ ⎟ ⎟ ⎟ ⎠
, where 0 is the null matrix of the appropriate size. If k ∈ {0, 1}, simply set M ∪ A g (α) ∶= M + diag(A g (α), 0, . . . , 0). The transition kernel eventually considered is

P ∶= ⋃ g∈K A g (α g ). (15)
Thanks to the constraint ∑ g∈G α g = 1, P is indeed a Markov transition kernel. However, the colored walk can now make steps that would not have been possible in the initial construction. For instance, it can go from (e, 1) to some (g, u) and then come back to (e, 1), even if p e = 0 for the initial walk. Therefore, the stopping times cannot be taken directly as the return times at color 1. Instead define, if Y n = (g n , u n ) has transition kernel P,

τ n ∶= ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ inf{m ≥ τ n-1 ∶ u m = 1, g m ≠ g τ n-1 } if g τ n-1 +1 ≠ g τ n-1 τ n-1 + 1 if g τ n-1 +1 = g τ n-1 .
Theorem 1 in the reversible case is now contained in the following lemma.

Lemma 7. Suppose X n is a finitely supported random walk on G defined by a probability vector p and started at e. Setting for each g ∈ K

α g ∶= ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ (1-pe) g pg ∑ h∈K h p h if g ≠ e p e if g = e ( 16
)
the preceding construction yields an operator P which defines a reversible colored random walk

(Y n ) n≥0 satisfying Y τn (d)
= X n for all n ≥ 0 if started at (e, 1).

Proof. As already pointed, the construction define a colored random walk as long as

∑ g∈S α g = 1,
which is true for α g defined as in [START_REF] Steven P Lalley | Finite range random walk on free groups and homogeneous trees[END_REF]. Furthermore such a colored walk is reversible: for all (g, u)

∈ G × [r], letting µ(g, u) = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 1 if u = 1 2 α h if u = u h (k) for some k < h .
defines a reversible measure for the random walk, as it can be checked directly. Consider now the colored walk (Y n ) n≥0 defined by ( 16), started at Y 0 = (e, 1). Suppose first that p e = 0, so that τ 1 is the hitting time of the set (K ∖ {e}) × {1}.

At step 1 the colored walk necessarily enters the segment joining (e, 1) to (h, 1) for some h ∈ K. If the walk escapes this segment at h, then Y τ 1 = h. Otherwise, it necessarily goes back to the starting state (e, 1). Now on each of these segments, the colored walk is simply performing a simple random walk so the escape probabilities are given by the standard gambler's ruin problem. Namely the simple random walk on [0 ∶ n] reaches n before it gets to 0 with probability k n when started at k ∈ [0 ∶ n]. Therefore by Markov's property

P (e,1) [Y τ 1 = g] = α g g + h∈K α h (1 -1 h )P (e,1) [Y τ 1 = g] .
We deduce that

P (e,1) [Y τ 1 = g] = α g g ∑ h∈K α h h = p g .
For the general case p e ≠ 0, Y τ 1 = (e, 1) if and only if Y 1 = (e, 1) which occurs with probability α e = p e . For g ≠ 0, consider the random walk conditionned to move at every step, written (Y ′ n ) n≥0 . If q(x, y) is the transition probability for Y n between two states x and y, then the transition probability for Y ′ n is 0 if y = x and q(x, y) (1-q(x, x)) otherwise. The previous argument apply to this walk, so

P (e,1) Y ′ τ ′ 1 = g = α g ((1 -p e ) g ) ∑ h∈K∖{e} α h ((1 -p e ) h ) = p g 1 -p e ,
with τ ′ 1 is the obvious extension of τ 1 to Y ′ n . Coming back to Y τ 1 : to reach g ≠ e it it is necessary that Y 1 ≠ e, which occurs with probability (1 -p e ). Conditional on that event it no longer matters whether the random walk comes back at e and possibly stays there, so one can reason with Y ′ n instead. Hence

P (e,1) [Y τ 1 = g] = (1 -p e )P (e,1) Y ′ τ ′ 1 = g = p g .
The conclusion follows.

Remark 3. The expected time E [τ 1 ], although not as simple as in the non-reversible case, can nonetheless be computed quite easily using for instance the electric network paradigm. Using [20, Prop 2.20], we found in the case p e = 0

E [τ 1 ] = g∈K p g g 2 = E X 1 2 . ( 17
)
Remark 4. In the initial construction, we have that the total number of colors is

r = 1 + g∈K ( g -1).
In the reversible construction, there is a factor 1 2 on front of the sum (because we use the same colors for g and g -1 ). In the improved construction of Subsection 2.1, this is an upper bound, the actual value is r = 1 + Card(K ′ ) -Card(K) where K ′ is the set of words which are a suffix of some element in K (in the chosen representatives). In a concrete application, it is often possible to design linearization procedures which are more economical in terms of number of colors, see Section 6 for an example.

Entropy and drift for colored random walks

In this section we extend the notions of entropy and drift to colored random walks, proving Proposition 2.

Transitivity properties. If (X n ) n≥0 is a Markov chain with transition kernel Q on a discrete state space V , (X n ) is said to be transitive if for all x, y ∈ V there exists a bijection ϕ ∶ V → V such that φ(x) = y and for all z ∈ V , Q(x, z) = Q(y, φ(z)). Transitivity has the consequence that the Markov chain can be translated in order to start on a specific state. Sometimes a weaker notion of transitivity is satisfied: there exists a finite partion of the state space such that a bijections as above exist only between states that are in the same set of the partition. In this case the Markov chain is said to be quasi-transitive.

Transitivity is an essential property of convolution random walks on groups, bijections being simply given by the left multiplications. It is the property that makes the sequences ( X n ) n≥0 and (H(X n )) n≥0 sub-additive and hence allows to define drift and entropy.

On the other hand, for colored random walks it is possible that no bijection as above exists between pairs (g, u) and (h, v) ∈ G × [r], but there is one between (g, u) and (h, u) for all g, h ∈ G, u ∈ [r], given by the left multiplication by hg -1 . Hence colored random walks are only quasi-transitive. For this reason it is slightly less straightforward to define entropy and drift for colored random walks than it is for convolution walks.

Let (X n ) n≥0 be a colored random walk defined by a family of matrices (p g ) g∈G . Thanks to quasi-transitivity it can be without loss of generality to be started at e ∈ G. Write P u = P (e,u) for the law of this colored chain when started at (e, u).

The definitions of entropy and drift can naturally be extended to colored random walks:

recall that if X n = (g n , u n ) ∈ G × [r], X n ∶= g n and set H u (X n ) ∶= - g,v P u [X n = (g, v)] log P u [X n = (g, v)] .
Let π be the unique invariant probability measure of the stochastic matrix P . Let P π denote the law of the colored Markov chain started at e with the starting color being chosen according to π, that is

P π = u∈[r] π(u)P u . Then H π (X n ) = ∑ u∈[r] π(u)H u (X n ) forms a sub-additive sequence. Indeed, for k ≤ n, the Markov property yields H u (X n X k ) = g,v P (e,u) (X k = (g, v))H v (X n-k ) = v P k (u, v)H v (X n-k ).
If we multiply by π(u) and sum over u ∈ [r], this proves that

H π (X n X k ) = H π (X n-k ) (18)
thanks to the invariance of π. Therefore one can bound

H π (X n+m ) ≤ H π (X n+m , X m ) = H π (X m ) + H π (X n+m X m ) = H π (X m ) + H π (X n ).
and prove the existence of the limit

h π ∶= lim n→∞ H π (X n ) n .
The previous computation is very simple but only give limits in expectation. By applying Kingman's subadditive theorem one can obtain L 1 as well as a.s. limits. Because the color set [r] is finite, one can also expect that the limits do not depend on the starting color in the case P is irreducible. This is exactly the content of Proposition 2. To prove this proposition, the following lemma will be needed: Lemma 8 ([20, Lemma 14.11]). Let (X n ) n be a Markov chain on a state space V and let f ∶ V N → R be a Borel function. If the law of f = f (X 0 , X 1 , . . .) does not depend on X 0 and f (X 1 , X 2 , . . .) ≤ f (X 0 , X 1 , . . .) a.s., then f is a.s. constant.

Proof of Proposition 2. We make use of the following explicit construction of the probability space. Let Ω ∶= (G × [r]) N , let F be the product sigma-algebra and θ ∶ (ω n ) n≥0 ↦ (ω n+1 ) n≥0 the shift operator. The coordinates of ω i ∈ G × [r] are written here ω i = (g i , u i ).

Consider the measure P g,u on Ω defined on cylinders by P g,u [ω 0 = (g 0 , u 0 ), ω 1 = (g 1 , u 1 ), . . . , ω n = (g n , u n )] = 1 g 0 =g,u 0 =u p g 1 (u, u 1 )⋯p gn (u n-1 , u n ).

Then X n ∶= (g 0 g 1 ⋯g n , u n ) is a realization of the colored random walk defined by p and P g,u is indeed the law of the random walk started at (g, u) where ω n is the pair generator-color chosen by the walk at time n.

Thanks to the invariance of π with respect to P , the measure

P πp ∶= g,u π(u)p g (u, v)P g,v
is invariant by the shift θ. Let P n g,u denote the law of X n under P g,u and consider the function f n on Ω defined by

f n = -log P n X 0 [X n ] .
By the Markov property,

P m+n X 0 [X m+n ] ≥ P m X 0 [X m ]P n Xm [X n+m ], so f n is sub-additive in the sense that f n+m ≤ f m + f n ○ θ m .
Because the walk is finitely supported, f 1 is integrable so Kingman's sub-additive theorem ensures that (f n n) converges both a.s. and in L 1 to a function f ∈ L 1 (P πp ), invariant under θ and such that

∫ f dP πp = lim n ∫ f n n dP πp = inf n ∫ f n n dP πp .
The last step is to use the lemma to prove that f is constant. By abuse of notation let us write f = f (X 0 , X 1 , . . .).

Since P n X 0 [X n ] ≥ P X 0 [X 1 ]P n-1 X 1 [X n ],
by taking logarithms and dividing by n, we get that a.s. f (X 1 , X 2 , . . .) ≤ f (X 0 , X 1 , . . .).

It then remains to see that the law of f does not depend on X 0 . Thanks to quasitransitivity, the law of f can only depend on the starting color. On the other hand the matrix P is irreducible so for all starting color u there exists a.s. a random integer m such that X m has color v. Suppose m is the first time color v is visited. Then, by the strong Markov property, for all n ≥ 0

P n+m e,u [X n+m ] ≥ P m e,u [X m ]P n gm,v [X n+m ] = P m e,u [X m ]P n e,v [ Xn ],
with Xn = ω m+1 ⋯ω n . Now take logarithms, divide by n and take n → ∞. The left-hand side converges a.s. to f ((e, u), . . .) while the right-hand side converges to f ((e, v), . . .). Thus a.s. we have f ((e, u), . . .) ≥ f ((e, v), . . .). By symmetry the converse inequality also holds true so there is in fact equality, which proves f is constant. Hence the entropy is well defined on almost all trajectory and does not depend on the starting color. The result is proved similarly for the drift.

Colored random walks on plain groups

Closed formulas for the drift and entropy of nearest-neighbor random walks on free groups were obtained in [START_REF] Vadim | Random walks on discrete groups: boundary and entropy[END_REF][START_REF] Derriennic | Quelques applications du théoreme ergodique sous-additif[END_REF][START_REF] Ledrappier | Some asymptotic properties of random walks on free groups[END_REF]. Similar approaches can be carried out for free products of finite groups, of monoids, of finite alphabets [START_REF] Lorenz | Rate of escape of random walks on free products[END_REF]7,[START_REF] Mairesse | Random walks on free products of cyclic groups[END_REF]. The case of free groups and free products of finite groups is very similar in nature and they can be handled together as done in [START_REF] Jean | Random walks on groups and monoids with a Markovian harmonic measure[END_REF]. As a preliminary step for closed formulas, in this section, we define and study the harmonic measure for colored random walks on plain groups. Let G 1 , . . . , G m be finite groups and consider the plain group

G = F d * G 1 * ⋯ * G m , with the set of generators S ∶= d ⋃ i=1 {a i , a -1 i } ⋃ ⎛ ⎝ m ⊔ j=1 S j ⎞ ⎠
, where for all j = 1, . . . , m, S j ∶= G j ∖{e}. Recall the definition of the map Next in [START_REF] Lorenz | Rate of escape of random walks on free products[END_REF]. Every element g ∈ G writes uniquely as a word g = g 1 ⋯g n with n = g and g i ∈ S, g i+1 ∈ Next(g i ) for all i. Such words will be called reduced.

If for all j = 1, . . . , m, G j = Z 2Z, then we say, with a slight abuse of vocabulary, that

G = F d * Z 2Z * ⋯ * Z 2Z
is a free group (two generators are free if there are not inverse).

The harmonic measure on the boundary

Consider a colored random walk (X n ) n≥0 on G×[r] defined by a family (p g ) of matrices. We assume that the walk is quasi-irreducible and nearest-neighbor. We assume furthermore that G is not isomorphic to Z or Z 2Z * Z 2Z. This implies the colored walk is transient, as will be proved in particular in Proposition 9 below. Define the boundary ∂G as

∂G ∶= {ξ 0 ξ 1 ⋯ξ n ⋯, ∀i ≥ 0, ξ i ∈ G, ξ i+1 ∈ Next(ξ i )} .
The multiplication action by G on itself can be extended to ∂G:

given g ∈ G, ξ = ξ 0 ξ 1 ⋯ ∈ ∂G, define gξ ∶= ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ gξ 0 ξ 1 ⋯ if ξ 0 ∈ Next(g) (gξ 0 )ξ 1 ⋯ if gξ 0 ∈ S ξ 1 ξ 2 ⋯ if g = ξ -1 1 . ( 19
)
The boundary ∂G, which can be seen as a subset of G N , is equipped with the product topology and the corresponding σ-algebra. Given a measure ν on ∂G, let g ⋅ ν be the image measure of ν under the mutiplication by g, that is the measure defined by the fact that

f (ξ) d(g ⋅ ν)(ξ) ∶= f (gξ) dν(ξ),
for all bounded measurable function f on ∂G.

Definition 5. A colored measure is a family ν = (ν u ) u∈[r] of probability measures on ∂G indexed by colors. A colored measure ν is stationary if for all u ∈ [r],

ν u = g∈G,v∈[r] p g (u, v) g ⋅ ν v . ( 20
)
Hence ν is also equal to the law X ∞ , which proves uniqueness of the stationary measure.

Markovian structure of the harmonic measure

A measure on ∂G is uniquely determined by its mass on cylinders. Given a measure ν, we will write ν(ξ 1 ⋯ξ n ) for the mass of the cylinder containing all infinite words which start with the prefix ξ 1 ⋯ξ n .

In the colorless case, the tree structure of the group G implies the harmonic measure is Markovian. It can be computed entirely from the solutions of a set of equations derived from the stationarity of the harmonic measure with the following interpretation.

For all k ≥ 0, let X

∞ be the restriction of X ∞ to the first k-th letters. Thus for all k ≥ 1 the mass under the harmonic measure of cylinders of size k is given by the law of X (k) ∞ . On the other hand (X (k) ∞ ) k≥1 is a non-backtracking walk which one can interpret as the loop-erased random walk formed from (X n ) n≥0 . In the standard colorless setting, the tree structure of the group makes the loop-erased random walk a Markov chain whose transition probabilities can be computed easily.

In the colored setting, one can expect to have similar properties but the loop-erased random walk of the process is no longer being a Markov chain and this is not the right process to consider. Instead let τ g ∶= inf{n ≥ 0, X n = (g, ⋅)} be the hitting time of g by the random walk X n and u k the color at time τ X (k) ∞ . Thus u k is the first color seen by the random walk X n when it visits the same element as the k-th step of X ∞ , but it is not necessary the color visited at the step X n where the k-th letter of walk starts coinciding with X (k) ∞ forever. Given g ∈ S, set

µ g (u, v) ∶= P (e,u) [X (1) ∞ = g, X τg = (g, v)]. (21)
In words, µ g (u, v) is the probability that the random walk, starting from (e, u), visits g, with color v for the first time, and later escapes at infinity in direction g. The process considered which is the equivalent of the loop erased random walk in the colored setting is (X

(k) ∞ , u k ) k≥1
, which is a colored Markov chain with increment distribution µ. As we shall check in Lemma 10, the family of matrices µ = (µ g ) g∈S is solution of the following set of matrix equations:

x g = p g ∆(x) g + h,h ′ ∈S hh ′ =g p h x h ′ + h∈Next(g) p h -1 x h ∆(x) -1 h x g , ∀g ∈ S, (22)
where ∆(x) g is the diagonal matrix with entries, for u ∈ [r],

∆(x) g (u, u) ∶= h∈Next(g) v∈[r] x h (u, v). (23)
gh = ξ 1 can only occur if g, h and ξ 1 belong to the same finite group G i , in which case Next(h) = Next(ξ 1 ). Combining these two observations, we find that a sufficient condition for stationarity is

ν ξ 1 = p ξ 1 ∆(ν) ξ 1 + g,h∈S gh=ξ 1 p g ν h + g∈S g -1 ξ 1 ∉S∪{e} p g ν g -1 ∆(ν) -1 g -1 ν ξ 1 .
This is precisely ensured by the fact that the ν g are solutions of [START_REF] James | Free probability and random matrices[END_REF]. Indeed, by construction, for a ∈ S,

Next(a) = {g ∈ S ∶ ag ∉ S ∪ {e}} and thus {g ∈ S ∶ g -1 ξ 1 ∉ S ∪ {e}} = Next(ξ -1 1
). Thus we just proved that for all g ∈ S, u ∈

[r], p ∞ u (g) = ∑ v∈[r] µ g (u, v) = ∑ v∈[r] ν g (u, v).
In particular, this yields that ∆ g = ∆(ν) g for all g ∈ S. Consequently the matrices µ g and ν g can be seen as the fixed points of a map f ∶ M = (M g ) g∈S ↦ (f (M ) g ) g∈S from the set of non-negative matrices to itself, where

f (M ) g ∶= A g + h,h ′ ∈S hh ′ =g p h M h ′ + h∈Next(g) p h -1 M h B g M g ,
for all g ∈ S, and A g , B g are non-negative matrices that do not depend on M .

One can now argue as in the proof of [START_REF] Jean | Random walks on groups and monoids with a Markovian harmonic measure[END_REF]Lem. 4.7] to deduce that µ g = ν g . Let ≤ be the coordinate-wise ordering for matrices: M ≤ N if and only if M (u, v) ≤ N (u, v) for all u, v ∈ [r]. Consider the matrices m g defined by

m g (u, v) ∶= µ g (u, v) ∧ ν g (u, v)
As each map f g ∶ M ↦ f (M ) g is obviously non-decreasing with respect to the coordinatewise ordering, one must have f (m) g ≤ f (ν) g = ν g and f (m) g ≤ f (µ) g = µ g for all g ∈ S, so f (m) ≤ m. By Brouwer's fixed point theorem, f must therefore admit another fixed point m ′ ≤ m. with the same properties as µ and ν. This m ′ is thus another solution of [START_REF] James | Free probability and random matrices[END_REF] and so must satisfy

∑ v∈[r] m ′ g (u, v) = ∑ v∈[r] µ g (u, v) for all u ∈ [r], but since m ′ ≤ m ≤ µ we deduce µ = m ′ = ν.
Hitting probabilities. Let us discuss here another way to compute the harmonic measure through hitting probabilities. It is less direct but we believe it makes the computation more natural in several examples such as free groups.

Given g ∈ G, u ∈ [r], recall that τ g is the hitting time of g. Let τ (g,u) ∶= inf{n ∶ X n = (g, u)} be the hitting time of a pair (g, u), so that τ g ∶= min u τ (g,u) . For g ∈ S, set

q g (u, v) ∶= P[τ g < ∞ and τ g = τ (g,v) ]. (26)
Observe that y g ∶= ∆ g 1 = µ g 1 and y g ∈ R r is equal to the diagonal of the diagonal matrix ∆ g . By construction, we have that ∑ g y g = 1. If we evaluate the matrix equation (31) on the vector 1, we obtain a linear equation for y = (y g ) g∈S , seen as a vector with coordinates in R r , of the form T y = 0 where T is matrix on S × S with matrix-valued coefficients in M r (R). Finally, once, ∆ g is known, Equation (31) becomes linear in µ seen as a vector of matrices.

Case of a free group. In some special cases, one can find additional relations allowing to write the matrix µ g as an explicit function of the matrices q g . This case occurs for instance when G = F d * Z 2Z * ⋯ * Z 2Z is a free group. Given g ∈ S, let d g be the diagonal matrix with diagonal entries

d g (u, u) ∶= w q g (u, w).
In words, d g (u, u) is the probability to ever reach g, starting from the pair (e, u).

Proposition 12. When G = F d * Z 2Z * ⋯ * Z 2Z is a free group, for all g ∈ S the matrix (I -q g -1 q g ) is invertible and

µ g (u, v) = q g (u, v) w∈[r] (I -q g -1 q g ) -1 (I -d g -1 )(v, w) ∀g ∈ S, u, v ∈ [r]. (32)
Proof. In the case of a free group, for all g ∈ S, u ∈ [r],

µ g (u, v) = q g (u, v) ⎛ ⎝ 1 - w∈[r] q g -1 (v, w) + w,z∈[r] q g -1 (v, w)µ g (w, z) ⎞ ⎠ .
In particular q g (u, v) = 0 implies µ g (u, v) = 0. Otherwise, rewrites this equation as

µ g (u, v) q g (u, v) = 1 -d g -1 (v, v) + w,z∈[r]
q g -1 (v, w)q g (w, z) µ g (w, z) q g (w, z) .

The right-hand being independant of u, so is the left-hand side. Consequently let x v ∶= µ g (u, v) q g (u, v). Then one can again rewrite the above equation as the matrix linear equation

x = (I -d g -1 )1 + q g -1 q g x
Provided Iq g -1 q g is invertible, solving this equation yields the desired expression for

µ g (u, v).
Therefore we are left to prove that Iq g -1 q g is invertible. This can be justified by the fact that ∑ v∈[r] ∑ n≥0 (q g -1 q g ) n (u, v) is the average number of times the walk goes to g -1 and comes back to e when starting at color u. By transience of the walk, this number must be finite. Hence the sum ∑ n≥0 (q g -1 q g ) n is convergent and the inverse of this matrix is precisely Iq g -1 q g . We now further study the matrix equation (26) satisfied by the hitting probabilities (q g ) g∈S in the case where G = F d * Z 2Z * ⋯ * Z 2Z is a free group. As already pointed, in this case, we have for all g ∈ S,

q g = p g + h≠g -1 p h -1 q h q g . (33)
In the colorless case, it is possible to reduce Equation (33) to a scalar equation, see for example [START_REF] Ledrappier | Some asymptotic properties of random walks on free groups[END_REF]. We extend this computation to the colored case. We define the matrix in

M r (R), z = I - g∈S p g -1 q g . (34)
We now express q g as a function of (z, p g , p g -1 ) and find a closed equation satisfied by z.

For simplicity, we assume that for all g ∈ G, the matrix p g is invertible. If this is not the case, a similar argument holds but one should be careful with pseudo-inverses. We define the matrices in M 2r (R):

P g = ⎛ ⎝ 0 p g p g -1 0 ⎞ ⎠ , Z = ⎛ ⎝ z 0 0 z ⎞ ⎠ and Q g = ⎛ ⎝ 0 q g q g -1 0 ⎞ ⎠ .
From our assumption, P g is invertible and

P -1 g = ⎛ ⎝ 0 (p g -1 ) -1 p -1 g 0 ⎞ ⎠
.

Applying (33) to g and g -1 , we find that, for all g ∈ S, zq g = p g -p g q g -1 q g and thus

ZQ g = P g -P g Q 2 g .
We set Z g = P -1 g Z. The above equation rewrites

(Z g + Q g )Q g = I. (35)
In particular Z g = Q -1 g -Q g so Z g and Q g commute. We may thus solve the quadratic equation Q 2 g + Z g Q g -I = 0 with Q g as unknown as in the scalar case. Completing the square yields

(Q g + Z g 2) 2 = I + Z 2 g 4.
Therefore, for some proper choice of the matrix square root function, we get

Q g = 1 2 * 4I + (P -1 g Z) 2 -P -1 g Z , (36)
where * √ ⋅ is a notation to stress that the choice of the square root is unknown. First, as Z g and Q g commute, the eigenvalues completely determine the square root. Also, since Q g is a block antidiagonal matrix, for every of its eigenvalue λ, -λ must also be an eigenvalue with the same multiplicity (algebraic and geometric). In particular, we are left with at most 2 r choices for the square root to pick in (36) (a choice of sign for each eigenvalue pair (λ, -λ)).

There is one useful property to further determine the square root. Consider

R g = Q g P -1 g = ⎛ ⎝ q g p -1 g 0 0 q g -1 p -1 g -1 ⎞ ⎠ .
We observe from (33) that q g p -1 g = (I -∑ h≠g -1 p h -1 q h ) -1 . The matrix ∑ h≠g -1 p h -1 q h is substochastic: it has non-negative entries and the sum over each row is less or equal than one (from a starting color, it corresponds to the probability that the colored walk killed when visiting g comes back to e after some time). In particular, the matrix ∑ h≠g -1 p h -1 q h has spectral radius less than one. Thus all eigenvalues of q g p -1

g and R g have positive real part. Using (34), the same argument shows that z and Z have all their eigenvalues with positive real parts.

Finally, from Equation (34), we have Z = I -∑ g P g Q g = I -∑ g P g R g P g . We deduce that

Z = I - 1 2 g∈S P g * 4I + (P -1 g Z) 2 -Z . (37)
Up to this issue of square root, we thus have found a fixed point equation satisfied by z (in Equation (37)) and expressed q g as a function of (z, p g , p g -1 ) (in Equation ( 36)). If r = 1, we can retrieve a known formula for colorless random walks. We note that Equation (37) should be compared to Proposition 3.1 in Lehner [START_REF] Lehner | Computing norms of free operators with matrix coefficients[END_REF] where a related formula is derived in a self-adjoint case (it can be checked that 2z is the inverse of the diagonal term of the Green function (I -P) -1 (e, e) where (I -P) -1 is seen as an infinite matrix indexed by G × G with coefficients in M r (C)).

5 Computing drift and entropy

Computation of the drift: proof of Theorem 4

A proof of Theorem 4 in the colorless case is given in [START_REF] Ledrappier | Some asymptotic properties of random walks on free groups[END_REF] for the free group. The proof can be adapted for more general free products, as mentionned in [START_REF] Jean | Random walks on groups and monoids with a Markovian harmonic measure[END_REF][START_REF] Mairesse | Random walks on free products of cyclic groups[END_REF]. It is also presented in a slightly different way in [START_REF] Lorenz | Rate of escape of random walks on free products[END_REF]. This is the latter proof that we here extend in the colored case.

Proof of Theorem 4. We aim to compute the limit of E X n n. This can be seen the Cesàro limit of the sequence (E X n+1 -E X n ) n≥0 . Here we deliberately omitted to precise the For colored random walks, the same computations can be made with matrices except that the cancellation between products no longer takes place. Instead, one has to deal with an infinite product of random matrices. For example, as one might guess from ( 19)-(30), it is true that

dgp ∞ v dp ∞ u (ξ) = lim n→∞ 1 ⊺ v q g -1 q ξ1 ⋯q ξn-1 µ ξn 1 1 ⊺ u q ξ1 ⋯q ξn-1 µ ξn 1 a.s., (41)
if ξ 1 ∈ Next(g -1 ). In the subsection, we prove that this kind of convergence holds and that the limit can be expressed thanks to random probability measure on [r] which is uniquely characterized by an invariance property.

Convergence in direction for inhomogeneous products of matrices

In this final subsection, we prove Theorem 6. The computation of the Radon-Nikodym derivatives in the integral formula of the entropy requires to investigate infinite products of random, non-negative matrices (that is, with non-negative entries). We use first use results for non-negative, deterministic matrices [24] to justify limits of infinite matrix products. This yields formulas like (41) and a first expression for the entropy (45). Then we use results for products of random matrices [START_REF] Bougerol | Products of random matrices with applications to Schrödinger operators[END_REF][START_REF] Carmona | Spectral theory of random Schrödinger operators[END_REF] to describe the law of the limits obtained, which yields eventually Proposition 6.

Convergence of the Radon-Nikodym derivatives. Instead of the general results in [24], it turns out that we can directly use a result from Lalley who already had to inquire about infinite matrix products in his study of finite range random walks [START_REF] Steven P Lalley | Finite range random walk on free groups and homogeneous trees[END_REF]. It does not seem however that his methods can be interpreted as an application of the linearization trick.

Let X be a finite set and Y a subset of X × X such that for all x ∈ X, the set {y ∈ X, (x, y) ∈ T } is non empty. Let Σ ∶= X Z be the space of doubly infinite sequences (ξ n ) n∈Z with values in X, such that (ξ n , ξ n+1 ) ∈ Y for all n ∈ Z. Let σ ∶ (ξ n ) n∈Z ↦ (ξ n+1 ) n∈Z denote the standard shift on Σ and given a function f ∶ Σ → C and n ∈ N, write

S n f ∶= f + f ○ σ + . . . f ○ σ n-1 .
Recall the definition of P + in [START_REF] Robert | Groups and simple languages[END_REF].

Proposition 15 ([16, Prop 5.2]). Let (M x ) x∈X be a family of r × r matrices with nonnegative entries. Assume there exists integers m ≥ 0, k ≥ 1 and a function B ∶ X k → 2 [r] ∖ {∅} (the set of non-empty subsets of [r]), such that for every n ≥ m and every family x 1 , . . . , x n+k ∈ X with (x i , x i+1 ) ∈ Y for all i,

(M x 1 M x 2 ⋯ M x n+k ) u,v > 0 ⇔ v ∈ B(x n+1 , . . . , x n+k ) ∀u, v ∈ [r] (42)
where B is a subset of B that depends only on the last k letters of g. This is exactly what is done in [START_REF] Steven P Lalley | Finite range random walk on free groups and homogeneous trees[END_REF]Proposition 5.3], under the condition that (Y n ) n≥0 is irreducible. We now come back to the proof of Proposition 17. As for the matrix H g , if g writes as a reduced word g = g 1 ⋯ g n , then we set q g = q g 1 ⋯ q gn , so one can argue as for the H g , namely prove that q g (u, v) > 0 for g large enough if and only if v is in some subset of [r] that depends only on the last letters of g.

The two constructions of the linearized random walks considered are made so that if Y 0 = e and X 0 = (e, 1), one can couple (X n ) n≥0 and (Y n ) n≥0 to have Y n = X τn where τ n always corresponds to a return time at color 1.

Moreover, colors are associated to elements of K: for all v ∈ [r], v ≠ 1, the colored walk X n , when at color 1, needs to be multiplied by specific elements of K in order to pass through the color v. More precisely there exists (at least one) h ∈ K with representative h = h 1 ⋯h k h k+1 ⋯h l , with the property that when at color 1, the random walk (X n ) reaches color v when being multiplied by h 1 ⋯h k . The main difference about the two constructions is the number of such h that one can associate to the color v, but this has no consequence for what follows.

Let K(v) be the set of such elements h.

For each h = h 1 ⋯h k h k+1 ⋯h l ∈ K(v), set p(h) ∶= h 1 ⋯h k and s(h) ∶= h k+1 ⋯h l .
By what precedes, to have color v when visiting g, X n has first to get to (gp(h) -1 , 1) for some h ∈ K(v), and then be multiplied by p(h). Arrived at g, it has no other choice then than to be multiplied by s(h).

The same goes for the starting color u: if the walk is at (e, u), then it is bound to arrive at (s(h ′ ), 1) for some h ′ ∈ K(u).

Thus using that X τn = Y n , one deduces that the colored random walk can go from (e, u) to (g, v) if and only if the finite range random walk can go from one of the s(h ′ ), h ′ ∈ K(u) to gp(h) -1 for some h ∈ K(v) and then to gs(h). Hence for any h

∈ K(v), h ′ ∈ K(u), q g (u, v) ≥ H g (s(h ′ ), s(h)).
Provided g is large enough, Equation (46) precisely states that the right-hand side is positive if and only if s(h) is in some subset of B that only depends on the last letters of g. Consequently the positivity of q g (u, v) does not depend on u for g large enough, which proves the result.

Law of Radon-Nikodym derivatives. The previous result is purely deterministic and does not take into account that the process (X

∞ , u n ) n≥0 is a Markov chain. Our goal in this paragraph is to determine the law of the probability vector V appearing in Corollary 16. The monograph [START_REF] Bougerol | Products of random matrices with applications to Schrödinger operators[END_REF] (see also [START_REF] Carmona | Spectral theory of random Schrödinger operators[END_REF]) state results for products of iid random matrices which, as we shall see, apply to Markovian products as well.

Remploying the general framework of Proposition 15, consider a Markov chain (Z n ) n≥0 on the finite state space X with transition matrix Q and Y ∶= {(x, y) ∈ X × X, Q(x, y) > 0}. Let (M x ) x∈X be a family of r × r non-negative matrices, such that condition (42) holds.

Consider the sequence defined by Y n ∶= M Zn , n ≥ 1. By Proposition 15, a.s. the product Y 1 ⋯Y n is non-zero and converges in direction to a rank one matrix spanned by a random vector V ∈ P + . If one multiplies the product on the left by another matrix M x , one still has a products of matrices M x , so one can expect the law of V to satisfy some invariance property. For all non-negative matrix A ∈ M r (R) and all z ∈ P + , we define Az to be the normalized image of z (identified with a vector in R r ) that makes it a probability vector, provided Az ≠ 0. The latter case will not be an issue: condition (42) implies in particular that matrices M x have no zero row, and vectors of P + have no zero coordinate so M x z is well defined for all x ∈ X, z ∈ P + .

Since Z n is a Markov chain, the law of V may depend on the starting state of Z n . Hence it is natural to think of it as a colored measure (colors being here the states x ∈ X). Definition 6. A family ν = (ν x ) x∈X of probability measure on P + is called a colored measure. Let Q * ν denote the colored measure defined by

f (z) d(Q * ν) x (z) = y f (M y z)Q(x, y) dν y (z)
for all bounded measurable function f on P + and x ∈ X. The colored measure ν is said to be invariant if Q * ν = ν. Lemma 18. Let ν x be the law of V when Z n is started at x, the colored measure (ν x ) x∈X is the unique colored measure which is invariant with respect to Q.

Proof. We use Markov property together with (44) to obtain the invariance of the law of V .

The proof of uniqueness is similar to the proof for the harmonic measure in Proposition 9. Consider another invariant colored measure (ρ x ) x∈X . By invariance, for all bounded measurable function f on P + the sequence

M n ∶= f (Y 1 ⋯ Y n w) dρ Zn (w), n ≥ 0
is a bounded martingale with respect to the filtration F n ∶= σ(Z 0 , Z 1 , . . . , Z n ), so M n converges a.s. and in L 1 . This being true for all bounded measurable function, this implies the measures Y 1 ⋯ Y n * ρ Zn converges weakly to a measure. Now, because the product Y 1 ⋯Y n converges in direction to V , the limit is necessarily the Dirac mass at V .

On the other hand, the martingale property with the L 1 convergence gives that for all bounded measurable functions f on P + , for all x ∈ X,

E x [f (V )] = E x f δ V = f dρ x .
Therefore ρ x must be the law of V when Z 0 = x, that is ρ x = ν x , and is consequently unique.

We are finally ready to prove Theorem 6.

Proof of Theorem 6. We apply Lemma 18 in the context of colored random walks, with

X = S × [r] and Q((g, u)(h, v)) = µ h (u, v).
Due to the form of the transition probabilities the law of V is only indexed by colors. It remains to use Corollary 16 in conjonction with the integral formula of the entropy given by Theorem 5.

Application

We now give an example of how the linearization trick can be used in order to compute the drift of a random walk. The example is simple enough so that the linearization trick is actually not needed. However it is a good illustration of its usefulness: whereas the direct computation requires some thought and can appear tedious, the linearization trick allows to hide all the technical aspects into matrix multiplications. The computation in the end is the same, but it can be handled quite smoothly with the linearization trick.

Let G 1 , G 2 be finite groups and consider the group G = G 1 * G 2 with the usual set of generators S = G 1 ⊔ G 2 ∖ {e}. Elements g of G can be written as words of length g with letters alternatively taking values in G 1 or G 2 .

Let k i denote the cardinality of G i ∖ {e}, i = 1, 2, L ≤ 1 be a fixed integer and consider the following random walk (X t ) t≥0 supported on the set of words of length smaller than L. At each step the walk is multiplied on the right by an element chosen uniformly among words of length n ≤ L that start with i ∈ {1, 2} with probability p i (n). In other words for all g = g i 1 ⋯g in of length n ≤ L, with i 1 , . . . , i n ∈ {1, 2}, i 1 ≠ i 2 ⋯ ≠ i n ,

p g = p i 1 (n) k i 1 ⋯k in ,
where p = (p i (n)) n≤L,i=1,2 is a probability vector : ∑ i,n p i (n) = 1. Of course in the denumerator above, one could regroup powers of k 1 , k 2 together. This random walk is the generalization of an example given in [START_REF] Mairesse | Random walks on free products of cyclic groups[END_REF] for which the drift is explicitly computed in the nearest-neighbor case L = 1.

As seen in the proof of Theorem 4, the drift is given by

γ = lim t→∞ 1 t t-1 k=0 E [ X k+1 -X k ] .
In this model, the knowledge of what group the last letters of X t belongs to is enough to determine the quantity Z t ∶= X t+1 -X t . Neglecting the case where X t or X t+1 og-f length smaller than L, Z t can thus be determined from a Markov chain on the state space {1, 2}.

The drift of X t can then be easily deduced from the stationary measure of this Markov chain. This is the computation done in [START_REF] Mairesse | Random walks on free products of cyclic groups[END_REF] for L = 1. This argument remains valid both for the finite support case L > 1 and for colored random walks. Hence the computation can be made with or without the linearization trick.

Direct computation. Given g ∈ G, let g, resp. g denote the first, resp. last letter of g. If g = e, g = g = 1. Suppose that at time t, X t > L so that neither in X t nor X t+1 can equal e.

At time t + 1, X t is multiplied by some element g. Here are the different cases occuring. If g is not in the same group as X t , there is no cancellation when concatenating X t and g, so X t+1 = X t g ends with the same letter as g, ie X t+1 = g. Otherwise there might be some cancellations and X t+1 = g if and only if there is no complete cancellation between X t and g. By complete cancellation we mean that g is exactly the inverse of the word formed by the g last letters of X t . If complete cancellation occurs, then X t+1 is bound not to be in the same group as g.

Since there are only two groups, g = g if and only if g is odd. Thanks to the simple form of the transition probabilities in this model, one can deduce thus deduce that the probability the last letter of X t goes from G 1 to G 2 is

Q 1,2 = n≥0 p 2 (2n + 1) + n≥0 p 1 (2n + 1) k n+1 1 k n 2 + n≥1 p 1 (2n)(1 - 1 k n 1 k n 2 ),
and the probability to stay in G 1

Q 1,1 = n≥2n+1 p 1 (2n + 1)(1 - 1 k n+1 1 k n 2 ) + n≥1 p 1 (2n) k n 1 k n 2 + n≥1 p 2 (2n).
The sums above are finite as p i (n) = 0 if n > L. By symmetry, exchange the roles of 1 and 2 to get Q 2,1 and Q 2,2 . In the end, one obtains a 2 × 2 stochastic matrix Q which is the transition matrix of the Markov chain induced by the last letter of X t in the sense that P X t+1 ∈ G j X t ∈ G i , X t > L = Q i,j for i, j ∈ {1, 2}. Since X t is transient it spends only a finite amount of time in the ball {g ∈ G, g ≤ L} so the ergodic theorem for Markov chains It is easy to see that ∑ g∈S pg is a stochastic matrix. Thus the matrices pg can be used to define a colored random walk (Y t ) t≥0 . In Equation (50), the color 0 is to be interpreted as a neutral color, while i 1 ⋯i n is to be interpreted as the "remaining step" for Y t , meaning that Y t will be mutliplied by successive elements of G i 1 , . . . , G in before it arrives at the color 0. For instance the probability to go from (e, 0) to (g, 212) with g ∈ G 1 is p 1 (4) k 1 . From (g, 212), the walk then goes to some (gh, 12), h ∈ G 2 with probability 1 k 2 , then to (ghg ′ , 1), g ′ ∈ G 1 with probability 1 k 1 and finally to (ghg ′ h ′ , 0) with probability 1 k 2 . Hence with probability p 1 (4) it moved between two states with color 0, from e to a uniform element of length 4 starting in group G 1 . This should make clear that that Y t linearizes the initial random walk X t in the sense of Theorem 1: if Y t starts at (e, 0), then it behaves exactly like X t when evaluated at the t-th return time at color 0.

Let us now apply the previous argument to this colored random walk. Let r be the number of colors used in the linearization and for i = 1, 2 set Pi ∶= ∑ g∈G i pg . When Y t is far from e, it induces a colored Markov chain on the state space {1, 2} × [r]. Because the random walk is nearest-neighbor, we are spared of all the considerations necessary to deal with finite support. The transition matrix we are looking for is simply

Q = ⎛ ⎝ (1 -1 k 1 )P 1 P 1 k 1 + P 2 P 1 + P 2 k 2 (1 -1 k 2 )P 2 ⎞ ⎠ (51)
which is the exact block analog of the matrix in [START_REF] Mairesse | Random walks on free products of cyclic groups[END_REF].

Likewise the change in distance is simply given by the matrix:

Q = ⎛ ⎝ 0 -P 1 k 1 + P 2 P 1 -P 2 k 2 0 ⎞ ⎠ . ( 52
)
The matrix Q defining an irreducible Markov chain, it admits a unique stationary measure π. As before, the ergodic theorem gives the drift of Y t as ∑ v∈[r] (π Q)(v) and by Theorem 1 the drift of X t is

γ = L n=1 p 1 (n) + p 2 (n) v∈[r] (π Q)(v).

Figure 1 :

 1 Figure1: Numerical simuation of a finite range random walk (X t ) t≥0 on F 2 = ⟨a, b⟩ with 12 generators of length 1, 2 and 3, and with random transition probabilities. The linearization procedure gives r = 16. On the left, an average of X t over n = 20000 trajectories compared to the line γt. On the right, an average of H(X t ) over n trajectories compared to the line ht. For computational efficiency, the entropy H(X t ) is approximated with the entropy of a random walk on [n] where λ(g), g ∈ {a, b}, are replaced by an independent uniform permutation matrix of size n (in other words, we consider a random action of F 2 on a set of size n). This approximation is valid as long as ht ≤ ln n, see [2].

The following result extends Theorem 1.12 in Ledrappier [START_REF] Ledrappier | Some asymptotic properties of random walks on free groups[END_REF] to colored random walks. The proof is exactly the same and is reproduced below. Proposition 9. There exists a random variable X ∞ ∈ ∂G such that X n converges a.s. to X ∞ . The law of X ∞ is called the harmonic measure and is the unique stationary colored measure on the boundary ∂G. It will be denoted (p ∞ u ) u∈ [r] where the index u is to be interpreted as the starting color of (X n ) n≥0 .

Proof. Consider the topology on ∂G defined by the distance d(ξ, ξ ′

) = e -ξ∧ξ ′ , with ξ ∧ ξ ′ being the length of the prefix common to ξ and ξ ′ . This topology makes ∂G a compact set so by the Lévy-Prokhorov theorem, the set P(∂G) of probability measures on ∂G is a non-empty convex and compact Hausdorff set when embedded with the weak-* topology. Let ζ ∶ ν u ↦ ∑ g∈G,v∈[r] p g (u, v)(g ⋅ ν v ). The multiplication in ∂G by an element of G being continuous, ζ is also a continuous map from P(∂G) to itself. By the Schauder-Tychonoff theorem, ζ admits a fixed point, which is exactly a stationary measure. Consider now a stationary measure ν. Since G is not isomorphic to Z or Z 2Z × Z 2Z the orbits under multiplication are dense in ∂G, that is for all ξ, ξ ′ ∈ ∂G and ∈ (0, 1) there exists g ∈ G such that d(gξ, ξ ′ ) < . From this we deduce that the only closed subsets of ∂G that are invariant under multiplication by G are the empty set and ∂G itself. In particular the support of ν must be ∂G and ν must be continuous: otherwise the set of points with the largest measure would be invariant and finite, so distinct from ∂G.

Stationarity implies that the sequence (X n ⋅ν) has the martingale property, in the sense that for every measure set A the sequence (X n ⋅ ν(A)) is a martingale. This martingale is positive and bounded, so (X n ⋅ ν) converges a.s. and in L 1 to a random measure Z. This implies in particular that a.s. X n → ∞. Indeed, one could otherwise extract a subsequence on which X n = g for some g ∈ G, with positive probability. Hence Z = g ⋅ ν and because ν is continuous and has support ∂G, this would imply X n → g and consequently X n would be stationary with positive probability. By the quasi-irreducibility assumption, the support of the colored walk is not reduced to e, so Borel-Cantelli lemma shows this is not possible. Note that X n → ∞ shows in particular that X n is transient.

We prove now that Z must be a Dirac mass. Since X n → ∞ and ν is continuous the measure under X n ⋅ ν of any cylinder has to tend to 0. Therefore the limit measure Z(ω) is exactly a Dirac mass on a point X ∞ (ω). This proves a.s. X n → X ∞ .

Markov property then shows that the law of X ∞ is indeed stationary. Finally by the martingale property and the L 1 convergence :

In the sequel, ∆(µ) g will be simply written ∆ g .

These equations generalize the so-called traffic equations of Mairesse [START_REF] Jean | Random walks on groups and monoids with a Markovian harmonic measure[END_REF]. Beware that the products are to be understood as matrix products. In particular one has to be careful not to change the order of the different terms when considering products.

Lemma 10. The family µ = (µ g ) g∈S is the unique family of matrices with non-negative entries which sum to a stochastic matrix and which is solution of Equation [START_REF] James | Free probability and random matrices[END_REF]. Moreover, for all starting color u ∈ [r] and all cylinder ξ 1 ⋯ ξ n ,

Proof. For n = 1 equation ( 24) is a consequence of the definition of the µ g . Now if n ≥ 2, the probability that X

u is just the probability the random walk escapes at infinity in direction ξ n , conditionned on the fact it cannot backtrack (in the group), that is

An immediate induction yields (24). Summing over colors then gives [START_REF] Woess | Random walks on infinite graphs and groups[END_REF].

Let us now prove now that the matrices µ g are characterized by Equation [START_REF] James | Free probability and random matrices[END_REF]. Consider any family (ν g ) g∈S of non-negative matrices, solutions of [START_REF] James | Free probability and random matrices[END_REF] and such that ∑ g∈S ν g is a stochastic matrix. Then for all u ∈ [r] define the measure ν ∞ u on ∂G by setting for each cylinder

The fact that ∑ g∈S ν g is a stochastic matrix proves that ν ∞ u is indeed a probability measure on ∂G.

Let us prove that the hypotheses on ν g necessarily imply

. By uniqueness of the harmonic measure, it suffices to show that ν ∞ is stationary. From ( 19)- [START_REF] Lyons | Probability on trees and networks[END_REF], to prove stationarity, we need to show that for all cylinder ξ 1 ⋯ ξ n , for all u ∈ [r],

We use the expression of ν ∞ in this equation and notice there are matrices appearing in both sides of the equation. Furthermore, the case where there exist g, h ∈ S such that Conditioning on X 1 and applying Markov property, one obtains that the family of matrices q = (q g ) g∈S satisfy the matrix equation

In the case where G = F d * Z 2Z * ⋯ * Z 2Z is a free group . This equation can again be found for classical nearest-neighbor random walks in [START_REF] Ledrappier | Some asymptotic properties of random walks on free groups[END_REF][START_REF] Jean | Random walks on groups and monoids with a Markovian harmonic measure[END_REF][START_REF] Mairesse | Random walks on free products of cyclic groups[END_REF] but here the equation is a matrix equation.

Lemma 11. The family q = (q g ) g∈S is the unique solution to Equation (27) among family of matrices

Proof. One can argue as in the proof of lemma 10 or the proof of [14, Lemma 4.7]: solutions of Equation ( 27) can be seen as fixed points of quadratic maps that are non-increasing with respect to the coordinate-wise ordering, which cannot have two fixed points.

The relation between the matrices q g and µ g is the following. Suppose the random walk is started at u. In order to have X

∞ = g, u 1 = v, the random walk has to visit g with first color v, which occurs with probability q g (u, v). Arrived at (g, v), it has to escape at infinity in some direction h ∈ Next(g). Hence by Markov property,

This gives yet another way to write equations ( 24) and ( 25):

Solving the traffic equations

General case. We have seen in the previous section that the harmonic measure is fully described by the family of matrices µ = (µ g ) g∈S on [r] defined by [START_REF] Mairesse | Random walks on free products of cyclic groups[END_REF]. By Lemma 10, these matrices are uniquely characterized by the traffic equation [START_REF] James | Free probability and random matrices[END_REF]. It is possible to evaluate numerically µ by iterating the map defining the traffic equations. The hitting probabilities q = (q g ) g∈S satisfy a simpler quadratic equation ( 27) than the traffic equation of µ. As explained in the proof of Lemma 11, it is possible to evaluate numerically from above and from below q by iterating the map f defined in (27) such that q = f (q). Moreover, once the hitting probabilities are computed, it is easy to compute µ. Indeed, using (28), the traffic equation reads ( 21)

starting color, as the final result does not depend on it by Proposition 2. In particular one can choose the starting color to be distributed according to the measure π. By Markov property and the invariance of π, for all n ≥ 0

We fix a color v. The random variable Z n ∶= gX n -X n takes values in {-1, 0, 1}. On the other hand, X n converges to the random variable X ∞ as n goes to infinity. Consequently gX n converges to gX ∞ ∈ ∂G and Z n converges to a random variable Z ∞ ∈ {-1, 0, 1}.

It is now easy to see what happens:

∞ ∈ Next(g) 0 otherwise

.

Hence, by the dominated convergence theorem, we find

µ h (v, w), as requested.

Entropy: : proofs of Theorem 5 and Theorem 6

The following computation is originally due to Kaimanovich and Vershik [START_REF] Vadim | Random walks on discrete groups: boundary and entropy[END_REF] and is here adapted to the matrix case. Given a discrete random variable X and a σ-algebra F, the conditional entropy of X with respect to F is defined as

Let T ∶= ⋂ n≥0 σ{X k , k ≥ n} be the tail σ-algebra. As one can check easily, the tail σ-algebra is also the σ-algebra generated by X ∞ . Therefore a function is T -measurable if and only if it writes as a function of X ∞ .

Proposition 13. The entropy of a colored random walk satisfies

Proof. By the Markov property for all n ≥ 1

When n → ∞ the left-hand side converges to H π (X 1 T ). On the other hand,

In the last line we have used equation [START_REF] Ledrappier | Some asymptotic properties of random walks on free groups[END_REF]. Since H π (X n ) n converges to h as n goes to infinity, one must also have that H π (X n ) -H π (X n-1 ) converges to h, hence the result.

Given a σ-algebra F and g, h ∈ G, u, v ∈ [r], let P [(g, u), (h, v) F] be the conditional transition probability with respect to F, that is

The stationarity of the harmonic measure

implies in particular that the measures g ⋅ p ∞ v are absolutely continous with respect to p ∞ u if p g (u, v) > 0.

Proposition 14. The conditional probabilities with respect to T are given by:

Sketch of proof. The result is true when replacing T with the invariant σ-algebra I which is the σ-algebra generated by all bounded invariant functions, that is, all bounded functions

. This is the content of [START_REF] Lyons | Probability on trees and networks[END_REF]Lemma 14.33]. Generally, the invariant and tail σ-algebras do not coincide but they do for transitive Markov chains, up to negligible sets. The proof goes basically like this: there is an equivalence between the set of bounded invariant functions and the set of bounded harmonic functions. There is a similar equivalence between bounded tail functions and bounded space-time harmonic functions. Using a zero-two law, one then shows that space-time harmonic functions do not actually depend on the time parameter and hence are classical harmonic functions. The equivalences between functions thus prove the equivalence of the σ-algebras. See [20, Section 14.6] for details.

For colored Markov chains, the arguments extend naturally, using quasi-irreducibility and quasi-transitivity. Therefore the above formula is correct with T instead of I.

Proof of Theorem 5. By Proposition 13 and Equation (39),

Now, using Proposition 14, we find

It concludes the proof.

Equation ( 10) is the matrix version of the known formula for colorless random walks [START_REF] Vadim | Random walks on discrete groups: boundary and entropy[END_REF][START_REF] Ledrappier | Some asymptotic properties of random walks on free groups[END_REF]. It shows that the computation of the entropy ultimately comes down to the computation of some Radon-Nikodym derivatives. In the colorless case, this computation goes basically as follows.

Consider a cylinder ξ 1 ⋯ξ n . Compute g ⋅ p ∞ (ξ 1 ⋯ξ n ) distinguishing the different cases occurring:

As one can check, the last case occurs if and only if ξ 1 ∈ Next(g -1 ). Expand now the expressions above into products using from (30) that p ∞ (ξ

,

As will be proved after, the left-hand side converges to the Radon-Nikodym derivative as n → ∞. One can then easily express the integral [START_REF] Lorenz | Asymptotic entropy of random walks on free products[END_REF] in terms of the scalars p g , q g and µ g and obtain the formulas given in [START_REF] Ledrappier | Some asymptotic properties of random walks on free groups[END_REF][START_REF] Mairesse | Random walks on free products of cyclic groups[END_REF].

Then there exist constants C > 0 and 0 < α < 1, maps ϕ, γ ∶ Σ → R and V, W ∶ Σ → P + such that for all ξ ∈ Σ,

where V = V (ξ 1 , ξ 2 , . . .) depends only on the "forward coordinates", while W = W (ξ 0 , ξ -1 , . . .) depends only on the "backward coordinates". Furthermore,

Proposition 15 states shows under condition (42), the product M ξ 1 M ξ 2 ⋯ M ξn tends up to renormalization factor to a rank one matrix whose range is spanned by the vector V (ξ). This result is well known for powers of a matrix with positive entries, in which case the vector V is nothing but the Perron-Frobenius eigenvector. Proposition 15 is thus a generalization of the Perron Frobenius theory to inhomogeneous products of non-negative matrices with possibly zero columns (condition (42)). We refer to [START_REF] Steven P Lalley | Finite range random walk on free groups and homogeneous trees[END_REF] for additional properties of the functions ϕ, γ with the vectors V, W which will not be needed here.

To apply Proposition 15 in context of linearized random walks, take X = S and (x, y) ∈ Y if and only if y ∈ Next(g).

Corollary 16. Suppose the matrices (q g ) g∈S satisfy the hypothesis of Proposition 15 and let V ∶ ∂G → P + be the corresponding map. Then for all u, v ∈

,

Proof. From ( 19)-(30), for any cylinder

Let ξ ∈ ∂G. Combining the previous computation with Proposition 15, there exist λ n > 0, uniformly lower bounded, and α < 1 such that if

The other cases are treated similarly.

On the other hand

u (ξ 1 ⋯ξn) dp ∞ u converges to the Dirac mass at ξ: for all integer k and > 0, the mass of all k-cylinders except the cylinder ξ 1 ⋯ ξ k is bounded by for n large enough. Thus the above limits give indeed the Radon-Nikodym derivative.

The next proposition asserts that for the colored random walks that we are mainly interested in, Corollary 16 applies.

Proposition 17. Suppose the colored random walk (X n ) n≥0 is a linearized random walk obtained from a finite range random walk (Y n ) n≥0 via one of the procedures presented in Section 2. If (Y n ) n≥0 is irreducible, then the matrices (q g ) g∈S , satisfy the hypothesis of Proposition 15.

Proof. Beware that the notations are the contrary to those of Section 2: here (X n ) n≥0 is the colored walk linearizing the finite range walk (Y n ) n≥0 .

Let us first review briefly a relevant argument in [START_REF] Steven P Lalley | Finite range random walk on free groups and homogeneous trees[END_REF]. Lalley proves that the hypothesis of Proposition 15 is satisfied by matrices H g which are related to the walk (Y n ) n≥0 . These matrices are defined as follows. Letting K denote the support of the finite range random walk (Y n ) n≥0 , define L ∶= max{ g , g ∈ K} and B ∶= {g ∈ G, g ≤ L}. The matrices H g will be taken in R B×B . Given g ∈ G, define

that is T g is the first time the representative of Y n writes as g times an element in B. When G is a plain group, representatives are unique so T g is well defined. For all a, b ∈ B, the (a, b)-entry of H g is then defined as

In [START_REF] Steven P Lalley | Finite range random walk on free groups and homogeneous trees[END_REF], Lalley only considers the case of a free group. The following properties can however be easily extended to plain groups.

The matrices H g , g ∈ S have the property that if g = g 1 ⋯ g n , then H g = H g 1 ⋯H gn , see [START_REF] Steven P Lalley | Finite range random walk on free groups and homogeneous trees[END_REF]Prop 2.3]. Thus proving that the family (H g ) g∈S satisfies condition (42) is equivalent to prove that there exists k ≥ 1 and B ∶ S k → 2 B ∖ {∅} such that for all g ∈ G with length

shows that the average amount of time X t is in G i converges to converges to π(i), where π is the unique invariant measure of the transition matrix Q. Now what is Z t ∶= X t+1 -X t ? Consider the cases previously identified. If g and X t belong to different group, then Z t = g . Otherwise, each cancellation occuring when concatenating X t and g make the distance decrease by one. Hence in case of complete cancellation Z t = -g . Otherwise, once the cancellations have been dealt with, the first step simply updates X t and consequently does not increase the distance, while the other remaining steps increase it by one. Therefore the contribution of g isg in case of complete cancellation and g -1 -2i otherwise, where i is the number of cancellations occurring when concatenating X t and g. Combining all these observations, the change in distance when going from group G 1 to group G 2 is Q1,2 = n≥0 (2n + 1)p 2 (2n + 1) -n≥0 (2n + 1) p 1 (2n + 1)

and when staying in G 1 :

Q1,1 = n≥2n+1 2n+1 i=1 (2n -2(i -1))p 1 (2n + 1) As before, Q2,1 , Q2,2 can be obtained by exchanging the roles of 1 and 2. In the end the drift of X t is given by γ = π(1)( Q1,1 + Q1,2 ) + π(2)( Q2,1 + Q2,2 ).

(49)

Computation with the linearization trick. Since we know specifically the random walk (X t ), we do not follow exactly the construction of the linearized random walk in Section 2 but adapt it to the example. What seems quite natural is the following: consider matrices pg = (p g (i 1 ⋯i n )) i 1 ⋯in indexed by reduced words i 1 ≠ i 2 ⋯ ≠ i n of length n ≤ L -1, including the case n = 0 of the empty word, written exceptionnally 0. For all g ∈ S and all reduced word i 1 ⋯i n of length n ≤ L -1, set pg (0, i

(50)