Combinatorics Meets Potential Theory

Abstract

Using potential theoretic techniques, we show how it is possible to determine the dominant asymptotics for the number of walks of length $n$, restricted to the positive quadrant and taking unit steps in a balanced set $\Gamma$.

The approach is illustrated through an example of inhomogeneous space walk. This walk takes its steps in $\{ \leftarrow, \uparrow, \rightarrow, \downarrow \}$ or $\{ \swarrow, \leftarrow, \nwarrow, \uparrow,\nearrow, \rightarrow, \searrow, \downarrow \}$, depending on the parity of the coordinates of its positions. The exponential growth of our model is $(4\phi)^n$, where $\phi= \frac{1+\sqrt 5}{2}$denotes the Golden ratio, while the subexponential growth is like $1/n$.

As an application of our approach we prove the non-D-finiteness in two dimensions of the length generating functions corresponding to nonsingular small step sets with an infinite group and zero-drift.