Random walks on Coxeter groups - MathOverflow

Random walks on Coxeter groups

2012-11-23T02:08:44Z

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$.

Answer by Andy Putman for Random walks on Coxeter groups

2012-11-24T04:12:21Z

Not an answer, but too long for a comment. There is actually a general recipe for computing the growth function of any Coxeter group (which implies, in particular, that it is always a rational function). I haven't done the calculation, but your purported calculation of the growth function for the Coxeter group you wrote down can be derived from this (assuming that it is true).

This is very old stuff. It appears as an exercise in Bourbaki's book "Groups et algebres de Lie"; see exercises 15-26 of Section 4.1. The details of these exercises appear in the paper

MR1170370 (93g:20081) Paris, Luis(CH-GENV-SM) Growth series of Coxeter groups. Group theory from a geometrical viewpoint (Trieste, 1990), 302–310, World Sci. Publ., River Edge, NJ, 1991.

The book this paper appears in is extremely hard to track down; as far as I can tell, it is not available anywhere at any price. It contains a number of important papers in geometric group theory, so I scanned it a long time ago. I just posted a scan of the above paper here.

Answer by Agol for Random walks on Coxeter groups

2012-11-24T19:05:49Z

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}.$$