# Random walks on Coxeter groups

Let $G_N$ be the group generated by elements $a_1,\ldots,a_N$ subject to the relations $a_i^2=1$ and $(a_ia_j)^3=1$. The growth function of $G_N$ is then $$f_N(t)=\frac{1+2t+2t^2+t^3}{1-Mt-Mt^2+\frac{M(M+1)}{2}t^3}$$ where $M=N-2$ (or at least, this seems to be the correct generalization of the $N=4,5$ known formulae, A154638 and A162740 @ OEIS). Question now: is the random walk function $$g_N(t)=\sum_{k=0}^\infty Card(i_1,\ldots,i_k|a_{i_1}\ldots a_{i_k}=1)\cdot t^k$$ known? Maybe related to $f_N$? I'd be actually interested in the $N\to\infty$ behavior of $g_N$.

-

For the case $N=3$, this is the random walk on the honeycomb lattice:

Lemma 2.1 in this paper computes the number of walks of length $2n$ on the honeycomb lattice which return to the origin, so $$g_3(t)=\sum_{n=0}^{\infty}\sum_{k=0}^n \binom{2k}{k}\binom{n}{k}^2 t^{2n}.$$

-
@Teo Banica : I don't know whether anyone has looked at the $N \rightarrow \infty$ behavior. My knowledge of this area comes via geometric group theory, where for a while there was a cottage industry proving that growth series for various kinds of group were rational or irrational (see the intro of my paper "The rationality of sol manifolds" from math.rice.edu/~andyp/papers for a bibliography). However, I'm not aware of a large literature for the sorts of finer questions you ask. –  Andy Putman Nov 24 '12 at 16:18