Search

This paper announces results which have been later developped in three articles: 1. "Random walks on groups and monoids with a Markovian harmonic measure", Electron. J. Probab., vol. 10, p. 1417-1441, 2005. 2. "Random walks on free products of cyclic groups", J. London Math. Society, vol. 75, n. 1, p. 47-66, 2007. 3. "Randomly growing braid on three strands and the manta ray", Ann. Appl. Probab., vol. 17, n. 2, p. 502-536, 2007.; We consider a transient nearest neighbor random walk on a group G with finite set of generators S. The pair (G, S) is assumed to admit a natural notion of normal form words which are modified only locally when multiplied by generators. The basic examples are the free products of a finitely generated free group and a finite family of finite groups, with natural generators. We prove that the harmonic measure is Markovian and can be completely described via a finite set of polynomial equations. It enables to compute the drift, the entropy, the probability of ever hitting an element, and the minimal positive harmonic functions of the walk. The results extend to monoids. In several simple cases of interest, the set of polynomial equations can be explicitly solved, to get closed form formulas for the drift, the entropy,... Various examples are treated: the modular group Z/2Z *Z/3Z, the Hecke groups Z/2Z *Z/kZ, the free products of two isomorphic cyclic groups Z/kZ *Z/kZ, the braid group B3 , and Artin groups with two generators.

International audience; In a heap model, solid blocks, or pieces, pile up according to the Tetris game mechanism. An optimal schedule is an infinite sequence of pieces minimizing the asymptotic growth rate of the heap. In a heap model with two pieces, we prove that there always exists an optimal schedule which is balanced, either periodic or Sturmian. We also consider the model where the successive pieces are chosen at random, independently and with some given probabilities. We study the expected growth rate of the heap. For a model with two pieces, the rate is either computed explicitly or given as an infinite series. We show an application for a system of two processes sharing a resource, and we prove that a greedy schedule is not always optimal.

The height of a trace is the height of the corresponding heap of pieces in X.G. Viennot's formalism, or equivalently the number of components in its Cartier-Foata decomposition. Let h(t) and ∣t∣ be, respectively, the height and the length of a trace t. We prove that the bivariate commutative series ∑tx ∣t∣yh(t) is rational, and we give a finite representation of it. As a by-product we obtain that the asymptotic average height of the traces of a given length is rational and explicitly computable. We show how to exploit the symmetries in the dependence graph to obtain representations of reduced dimensions of the series. For highly symmetric trace monoids, the computations may become very effective. To illustrate this point, we consider the family of trace monoids whose dependence graphs are triangular graphs, i.e., line graphs of complete graphs. We study the combinatorics of this case in details.

Given an Iterated Function System (IFS) of topical maps verifying some conditions, we prove that the asymptotic height optimization problems are equivalent to finding the extrema of a continuous functional, the average height, on some compact space of measures. We give general results to determine these extrema, and then apply them to two concrete problems. First, we give a new proof of the theorem that the densest heaps of two Tetris pieces are sturmian. Second, we construct an explicit counterexample to the Lagarias-Wang finiteness conjecture for the joint spectral radius of a set of matrices. Résumé. Etant donné un système itéré de fonctions (IFS) topicales, vérifiant certaines conditions, nous montrons que les questions d’optimisation asymptotique de la hauteur sont équivalentes à la recherche des extrema d’une fonctionnelle continue, la hauteur moyenne, sur un certain espace compact de mesures. Nous présentons des résultats généraux permettant de déterminer ces extrema, puis appliquons ces méthodes à deux problèmes concrets. Premièrement, nous redémontrons que les empilements les plus denses de deux pièces de Tetris sont sturmiens. Deuxièmement, nous construisons un contre-exemple effectif à la conjecture de finitude de Lagarias et Wang sur le rayon spectral joint d’un ensemble de matrices.

We consider an infinite tandem queueing network consisting of ./GI/1 stations with i.i.d. service times. We investigate the asymptotic behavior of t(n,k), the inter-arrival times between customers n and (n+1) at station k, and that of w(n,k), the waiting time of customer n at station k. We establish a duality property by which w(n,k) and the ``idle times'' y(n,k) play symmetrical roles. This duality structure, interesting by itself, is also instrumental in proving some of the ergodic results. We consider two versions of the model: the quadrant and the half-plane. In the quadrant version, the sequences of boundary conditions {w(0,k), k in N} and {t(n,0), n in N}, are given. In the half-plane version, the sequence {t(n,0), n in Z} is given. Under appropriate assumptions on the boundary conditions and on the services, we obtain ergodic results for both versions of the model. For the quadrant version, we prove the existence of temporally ergodic evolutions and of spatially ergodic ones. Furthermore, the process {t(n,k), n in N} converges weakly with k to a limiting distribution, which is invariant for the queueing operator. In the more difficult half plane problem, the aim is to obtain evolutions which are both temporally and spatially ergodic. We prove that [1/n \sum_{k=1}^n w(0,k) ] converges almost surely and in L1 to a finite constant. This constitutes a first step in trying to prove that {t(n,k), n in Z} converges weakly with k to an invariant limiting distribution.

We consider the iterates of bilinear functions over the semiring (max, +). Equivalently, our object of study can be viewed as recognizable tree series over the semiring (max, +). In this semiring, a fundamental result associates the asymptotic behaviour of the iterates of a linear function with the maximal average weight of the circuits in a graph naturally associated with the function. Here we provide an analog for the 'iterates' of bilinear functions. We also give a triple recognizing the formal power series of the worst case behaviour. Remark. Due to space limitations, the proofs have been omitted. A full version can be obtained from the authors on request.