Random walks on Coxeter groups

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.

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

           (source)

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