Cyril Banderier, Projet Algorithmes, Inria.

De l'algébricité des séries génératrices de marches aléatoires unidimensionnelles

We prove that counting generating functions of 1-dimensional walks with a finite set of jumps allowed are algebraic. We extend this to walks with all backwards jumps allowed and relate the theory to random generation and enumeration by means of "generating trees". Functional equations of 2-dimensional can also be solved with the "kernel method" (we give an example with knight moves). We finally establish asymptotics of paths and excursions of our 1-dimensional walks by analysis of singularities or saddle point methods.