On the Asymptotics and the Non-Holonomic Character of First Returns in the Standard Euclidean Lattice

Abstract

We give precise asymptotics to the number of first time returning random walks in the standard orthogonal lattice in $\mathbb{R}$ and we prove that these numbers do not form a $P$-recursive sequence. In the process, the known asymptotics of the number of closed walks are obtained in an elementary way, by using a combinatorial and geometric multiplication principle together with the classical theory of Legendre polynomials. By showing that the relevant generating functions are $G$-functions, we use a form of the Hadamard convolution to find their singularities in all dimensions and give the ODEs that they satisfy for $d\le 5$, some of which seem to be new. We use the Lucas property of the number of closed walks to prove that the corresponding generating function is not invertible as a $G$-function, which immediately implies that the generating function of the first time returning walks is not holonomic. We propose a few conjectures on the form of the asymptotic coefficients and of the ODEs.

34 pages, 5 figures