# Journal of Combinatorial Algebra

Full-Text PDF (273 KB) | Metadata | Table of Contents | JCA summary

**Volume 1, Issue 2, 2017, pp. 127–144**

**DOI: 10.4171/JCA/1-2-1**

Published online: 2017-04-06

Words in linear groups, random walks, automata and P-recursiveness

Scott Garrabrant^{[1]}and Igor Pak

^{[2]}(1) UCLA, Los Angeles, USA

(2) UCLA, Los Angeles, USA

Let $S$ be a generating set of a finitely generated group $G = \langle S \rangle$. Denote by $a_n$ the number of words in $S$ of length $n$ that are equal to 1. We show that the *cogrowth sequence* $\{a_n\}$ is not always P-recursive. This is done by developing new combinatorial tools and using known results in computability and probability on groups.

*Keywords: *Cogrowth sequence of groups, probability of return, P-recursive sequences, linear groups, finite state automata

Garrabrant Scott, Pak Igor: Words in linear groups, random walks, automata and P-recursiveness. *J. Comb. Algebra* 1 (2017), 127-144. doi: 10.4171/JCA/1-2-1