# Is random walk drift rational?

(Question mildly edited for clarity by request of Matt F.)

If $$G$$ is a finitely presented group, let $$|\cdot|$$ denote the word metric with respect to a finite set of generators. Suppose $$\nu$$ is a finitely supported measure on $$G$$ with rational weights. A random walk on $$G$$ is built by at each stage multiplying by an element of $$G$$, selected independently from $$\nu$$. The drift is defined to be the $$\nu^{\mathbb N}$$-a.s limit of $$|g_1g_2\ldots g_n|/n$$.

Does there exist a finitely-presented $$G$$ and a rational $$\nu$$ so that $$d$$ is irrational?

For nearest neighbour random walks on certain free products the rate of escape (or, if you wish, drift) was explicitly calculated by Mairesse and Matheus. In particular, their formula (26) gives an example of a "rational" random walk on the free product of $$\mathbb Z_2$$ and $$\mathbb Z_3$$ (i.e., essentially, on $$SL(2,\mathbb Z)$$) with an irrational rate of escape. Yet another (maybe even more explicit) example is provided by formula (28) for the group $$\mathbb Z_3*\mathbb Z_3$$. I am pretty sure that such examples abound for nearest neighbour random walks on free groups as well - it should be easy to check by using the description of the harmonic measure (which goes back to Dynkin and Malyutov, 1961) and the resulting formula for the rate of escape.

• So it appears that the rates in that paper are at least algebraic- do you happen to know if there’s a counterexample to that also? – Anthony Quas Sep 19 '19 at 5:43
• This is a good question. I am not aware of any examples. Already the case of a free group with the step distribution which is finitely supported but not concentrated on the generating set is not obvious at all. A broader context can be provided by the questions about algebraicity of the growth rate of the underlying group or about the spectral radius of the random walk. – R W Sep 19 '19 at 15:03

For a random walk of $$n$$ steps on a square lattice, I calculate an expected distance of $$2\sqrt{n/\pi}$$ in this metric. This has the transcendental coefficient that you ask for in a comment, with a different exponent than you were expecting.

Let $$G=\mathbb{Z}^2$$, where $$|(x,y)|=|x|+|y|$$ is the norm with respect to the generators $$(\pm1,0)$$ and $$(0,\pm1)$$. Let $$\nu$$ give weight $$1/4$$ to each of those generators. We focus on $$x$$-steps and $$x$$-distances, i.e. steps and distances in the direction of the $$x$$-axis.

After $$k$$ $$x$$-steps, the $$x$$-position is distributed roughly as $$N(0,\sqrt{k})$$, and the expected $$x$$-distance from the origin is roughly $$\sqrt{2k/\pi}$$.

After $$n$$ steps total, the number $$k$$ of $$x$$-steps is distributed as $$B(n,1/2)$$, so the expected $$x$$-distance from the origin is roughly $$\sqrt{n/\pi}$$. Thus the expected total distance from the origin is roughly $$2\sqrt{n/\pi}$$.

• If I understood the question correctly, the drift in this case is zero: the distance grows as $\sqrt{n}$ rather than $n$. – Mateusz Kwaśnicki Sep 19 '19 at 9:30
• What about $\mathbf{F}_2 \wr \mathbf{Z}^2$? – Sean Eberhard Sep 19 '19 at 10:55
• @MateuszKwaśnicki, the phrase “one has” suggests that a result follows. If what follows that phrase is actually a definition, then something beginning with “let” would be better. – Matt F. Sep 19 '19 at 12:30
• @SeanEberhard: I believe your group is the lamplighter on $\mathbb Z^2$? In that case, if $\nu$ is uniform on the generators and their inverses, the drift is zero. Not sure about other $\nu$... – Anthony Quas Sep 19 '19 at 13:43
• @MattF.: as Mateusz says, I really did have in mind ballistic (SLN) growth rather than diffusion (CLT) here. Sorry if this wasn’t clear. – Anthony Quas Sep 19 '19 at 13:45