Let $G$ be an infinite group with a finite generating set $S$. For $n \geq 1$, let $p_n$ be the probability that a random word in $S \cup S^{-1}$ of length at most $n$ represents the identity. Is it possible for $p_n$ to not go to $0$ as $n$ goes to $\infty$?
10
-
1$\begingroup$ @BenjaminSteinberg: I'm not sure I follow. Those seem to be about random walks on the Cayley graph of a free group, and the relevant probabilities seem to decay to $0$. Do you mean that we should write $G = F_n/K$ and think about whether a random walk in $F_n$ will land in $K$? I will have to think more about what exactly the answers are saying, but if they do answer my question it seems that they will give the answer "no" rather than "yes", right? $\endgroup$– XiyanCommented Oct 14, 2022 at 0:15
-
3$\begingroup$ If one averages over all $k^n$ words ($k=|S\cup S^{-1}|$) of length $=n$, one gets the probability of return $p'_n$. Indeed it is known that $p'_n\to 0$ for an infinite group. Here $p_n=(\sum_{i=0}^n k^i p'_n)/(\sum_{i=0}^n k^i)$, it follows that $p_n$ also tends to zero. $\endgroup$– YCorCommented Oct 14, 2022 at 2:28
-
2$\begingroup$ I think the keyword you need is “cogrowth” of a group. There are many papers on the subject. $\endgroup$– HJRWCommented Oct 14, 2022 at 5:45
-
2$\begingroup$ @HJRW: Thanks, that keyword gave me exactly what I want! The result I was looking for is contained in Woess, Wolfgang, Cogrowth of groups and simple random walks. Arch. Math. (Basel) 41 (1983), no. 4, 363–370. $\endgroup$– XiyanCommented Oct 14, 2022 at 16:38
-
1$\begingroup$ but the phrase "probability of return" might help finding references (I don't have them in mind now) $\endgroup$– YCorCommented Oct 14, 2022 at 16:41
|
Show 5 more comments
1 Answer
$\begingroup$
$\endgroup$
5
The answer is "no", and it has nothing to do with free groups, cogrowth, or Schreier graphs. We are talking here about the return probabilities of the simple random walk on $G$ (i.e., the one whose step distribution is equidistributed on the set $S\cup S^{-1}$). The reason is the following simple property differentiating finite and infinite groups: the random walk on a countable group $G$ determined by a step distribution $\mu$ has a finite stationary measure if and only the group is finite (under, for simplicity, the assumption that the random walk is non-degenerate, i.e., the support of the step distribution generates the whole group as a semigroup), and this distribution is then uniform.
The argument is very simple: if a stationary distribution is finite, then it has a maximal weight atom, and then by the maximum principle the weights of all other atoms have to be same. Or, instead of stationary measures one can argue in terms of harmonic functions, then the claim is that the finite groups are the only ones that admit summable harmonic functions (which are constants).
Thus, one can not have a positively recurrent random walk on an infinite group, which by general Markov theory (e.g., see Theorem 1.8.5 in Norris' textbook) implies the answer.
EDIT This argument only uses that the transition matrix of a random walk on a group is bi-stochastic, i.e., that the counting measure on the state space is stationary. The underlying general fact is then: if a Markov chain has an infinite stationary measure, then it can not be positively recurrent.
-
4$\begingroup$ Very nice! Your first sentence is not correct, though: the question has something to do with all those things. $\endgroup$– HJRWCommented Oct 16, 2022 at 6:11
-
$\begingroup$ @HJRW - I honestly fail to see this: the argument is much more general. I will add a comment about it. $\endgroup$– R WCommented Oct 16, 2022 at 12:16
-
$\begingroup$ The proof can be phrased without mentioning these things, but it's not correct to say that it has "nothing to do with them". Your argument happens on a Cayley graph, a kind of Schreier graph. The generating set can be equivalently thought of as an epimorphism $q:F\to G$ where $F$ is a free group, and the question equivalently asks for the probability that a random element of $F$ is in $\ker q$. The cogrowth measures the density of $\ker q$ in $F$, so is intimately related to this. (Indeed, the OP found the answer in a paper on cogrowth before you posted your answer.) $\endgroup$– HJRWCommented Oct 17, 2022 at 7:38
-
$\begingroup$ @HJRW - To quote Bertrand Russell, "Occam's razor entia non multiplicanda praeter necessitatem is [...] the supreme methodological maxim in philosophizing." $\endgroup$– R WCommented Oct 17, 2022 at 22:32
-