MATHEMATICS

E. B. DYNKIN and M. B. MALYUTOV

RANDOM WALK ON GROUPS WITH A FINITE NUMBER OF GENERATORS

(Presented by Academician A. N. Kolmogorov, 18 XI 1960)

1. Let \(G\) be a group with a finite number of generators \(a_1, a_2, \ldots, a_m\)*. Put \(a_{-i}=a_i^{-1}\) \((i=1,2,\ldots,m)\). Suppose positive numbers \(p_i\) \((i=\pm 1,\pm 2,\ldots,\pm m)\) are given such that

\[ \sum_{i=-m}^{m} p_i = 1 . \]

By a random walk on the group \(G\) we mean a Markov chain with phase space \(G\) and transition probabilities \(p(g,h)=p_i\), if \(h=ga_i\) \((i=\pm 1,\pm 2,\ldots,\pm m)\); \(p(g,h)=0\) in the remaining cases. In particular, if the generators \(a_1,a_2,\ldots,a_m\) commute with one another and there are no other relations between them, we obtain the random walk on the \(m\)-dimensional lattice studied by many authors.

In this note, for a random walk on groups with a finite number of generators, the Martin boundary is studied and all positive harmonic functions are constructed. In addition, one general theorem is proved on harmonic functions on sets with a transitive nilpotent group of transformations.

1. Let \(E\) be some finite or countable set. Consider a homogeneous Markov chain on \(E\) with transition probabilities \(p(x,y)\) \(\bigl(x,y\in E,\ p(x,y)\ge 0,\ \sum_{y\in E}p(x,y)=1\) for all \(x\in E\bigr)\). A function \(f(x)\) on \(E\) is called harmonic (with respect to \(p(x,y)\)) if, for every \(x\in E\),

\[ \sum_{y\in E} p(x,y) f(y)=f(x). \]

Theorem 1**. Let \(G\) be a nilpotent group acting transitively on a set \(E\). Suppose an irreducible Markov chain with transition probabilities \(p(x,y)\), invariant with respect to \(G\) (i.e. \(p(gx,gy)=p(x,y)\) for all \(g\in G,\ x,y\in E\)), is given on \(E\). Then every bounded harmonic function on \(E\) is constant.

The proof is based on the following lemma:

Lemma 1. If \(G\) is an arbitrary group, and all the remaining conditions of Theorem 1 are satisfied, then every bounded harmonic function on \(E\) is constant on the transitivity classes of \(E\) with respect to the center \(Z\) of the group \(G\).

Proof of the lemma. If \(f(x)\) is a harmonic function and \(|f(x)|<C\) for all \(x\in E\), then for every \(g\in Z\), \(\varphi(x)=f(x)-f(gx)\) is also a harmonic function; moreover, for any \(x\in E\) and \(m>0\),

\[ \left|\sum_{k=0}^{m} \varphi(g^k x)\right| = |f(x)-f(g^{m+1}x)| < 2C . \]

* For definitions of the algebraic concepts used in the present note, see, for example, (2).

** For the case where \(E\) is the \(m\)-dimensional lattice and \(G\) is the group of all its parallel translations, this theorem was proved by A. M. Leontovich.

Suppose that \(\sup_{y\in E}\varphi(y)=M>0\) (the case \(\sup_{y\in E}(-\varphi(y))=-\inf_{y\in E}\varphi(y)>0\) is treated analogously). Choose \(N\) so that \(N\cdot M/2>2C\). For any \(n<N\) there is a \(k_n>0\) such that \(p^{(k_n)}(x,g^n x)=p_n>0\) for every \(x\in E\) (\(p^{(k)}(x,y)\) denotes the probability of transition from \(x\) to \(y\) in \(k\) steps). Put \(p=\min_{n<N}p_n\). Let \(\varphi(x)>(1-p/2)M\). Then we obtain
\[ \left(1-\frac{p}{2}\right)M<\varphi(x)=\sum_{y\in E}p^{(k_n)}(x,y)\varphi(y)\leq p\varphi(g^n x)+(1-p)M\quad(n<N), \]
whence \(\varphi(g^n x)>M/2\) \((n<N)\). Hence,
\[ \sum_{k=0}^{N-1}\varphi(g^k x)>2C, \]
and we have obtained a contradiction.

Proof of the theorem. Form the sequence of groups
\[ G_i=G_{i-1}/Z_{i-1}, \]
where \(Z_{i-1}\) is the center of the group \(G_{i-1}\) (we take \(G_0=G\)). A group is called a nilpotent group of class \(n\) if \(G_n=\{e\}\), while \(G_{n-1}\ne\{e\}\). We shall carry out the proof by induction on \(n\). For \(n=0\), \(G=\{e\}\), the space \(E\) consists of one point, and the assertion of the theorem is trivial. Suppose that for all \(n<N\) the theorem is true. We shall prove the theorem for \(n=N\). To this end note that \(\widetilde G=G/Z\) is a nilpotent group of class \(N-1\). Let us call the orbits of the group \(Z\) the subsets of the space \(E\) of the form \(Zx\) \((x\in E)\). Denote the set of orbits by \(\widetilde E\). Note that the sum
\[ \sum_{z\in Z}p(x,zy) \]
depends only on the orbits \(Zx, Zy\), and not on the elements \(x,y\) themselves. Denote this sum by \(\widetilde p(Zx,Zy)\). The function \(\widetilde p(\widetilde x,\widetilde y)\) \((\widetilde x,\widetilde y\in \widetilde E)\) is nonnegative, and for any \(\widetilde x\in\widetilde E\)
\[ \sum_{\widetilde y\in\widetilde E}\widetilde p(\widetilde x,\widetilde y)=1. \]
It may be regarded as the transition function of some irreducible Markov chain in the space \(\widetilde E\). The group \(\widetilde G\) acts transitively on \(\widetilde E\) and leaves the function \(\widetilde p(\widetilde x,\widetilde y)\) invariant. Let a bounded harmonic function \(f(x)\) be given on \(E\). By Lemma 1 it is constant on each orbit \(Z\). Therefore the formula \(\widetilde f(Zx)=\widetilde f(\widetilde x)\) defines a function on \(\widetilde E\). This function is bounded and harmonic with respect to \(\widetilde p(\widetilde x,\widetilde y)\). By the induction hypothesis it is constant. Consequently, the function \(f(x)\) is constant on \(E\).

Theorem 1 ceases to be true if the nilpotency requirement on the group \(G\) is dropped. Thus, for a random walk on a free group with \(m\) generators \((m>1)\), where for all \(i\), \(p_i=1/2m\), one can define a nonconstant bounded harmonic function by the formula
\[ f(e)=0;\qquad f(a_{i_1}a_{i_2}\ldots a_{i_n})=\sum_{k=0}^{n-1}\frac{1}{(2m-1)^k},\quad \text{if } i_1>0; \]
\[ f(a_{i_1}a_{i_2}\ldots a_{i_n})=-\sum_{k=0}^{n-1}\frac{1}{(2m-1)^k},\quad \text{if } i_1<0, \]
where \(a_{i_1},\ldots,a_{i_n}\) is the minimal representation of the element \(g\).*

3. Denote by \(u(x,y)\) the probability, starting from \(x\), of ever hitting \(y\). For a random walk on a group with a finite number of generators, the probability \(u(x,y)\) is invariant under left translations,
\[ u(gx,gy)=u(x,y). \]

Theorem 2. A random walk on a free group with \(m>1\) generators is a transient Markov chain. The probabilities \(u_i=u(e,a_i)\)

* We say that \(a_{i_1}\ldots a_{i_n}\) is a minimal representation of the element \(g\) if \(g=a_{i_1}\ldots a_{i_n}\) and \(g\) cannot be represented as a product of fewer than \(n\) generators.

form the unique solution in the domain \(U=\{0<v_i<1;\ i=\pm1,\ldots,\pm m\}\) of the system of equations

\[ v_i=p_i+v_i\sum_{j\ne i}p_jv_{-j}\qquad (i=\pm1,\ldots,\pm m). \tag{1} \]

Proof. It is not hard to verify that the probabilities \(u_i\) satisfy the system (1) and, if the chain is transient, then \(\{u_i\}\in U\). Put

\[ F(x)=1+(m-1)x-\sum_{i=1}^{m}\sqrt{x^2+4p_ip_{-i}},\qquad v_i(x)=\frac{1}{2p_{-i}}\left(-x+\sqrt{x^2+4p_ip_{-i}}\right). \]

It is easy to verify that if \(F(\gamma)=0\), then \(v_i(\gamma)\) \((i=\pm1,\ldots,\pm m)\) is a solution of the system (1). Note that \(F(x)\) is concave upward, \(F(0)\ge0\), \(F'(0)>0\), \(F(1)<0\). Therefore there is one and only one number \(\gamma\in(0,1)\) such that \(F(\gamma)=0\). The possible sets of probabilities \(p_i\) \((i=\pm1,\ldots,\pm m)\) fill the \((2m-1)\)-dimensional open simplex \(T\). It is not hard to show that \(\gamma=\gamma(p)\) is a continuous function of \(p\in T\). Consequently the functions \(\tilde v_i(p)=v_i[\gamma(p)]\) are also continuous. Obviously, \(\tilde v_i(p)>0\) for all \(p\).

Denote by \(q\) the point of \(T\) with coordinates \(p_i=1/2m\) \((i=\pm1,\ldots,\pm m)\). It is checked directly that \(\tilde v(q)=\max_i \tilde v_i(q)=1/(2m-1)\). Let us show that \(\tilde v(p)<1\) for all \(p\). Indeed, otherwise we would have \(\tilde v(p^0)=1\) for some \(p^0\in T\). From the system (1) it follows that \(\tilde v_i(p^0)=1\) for all \(i\). It is not hard to show that for all \(x\)

\[ 1-\sum_{i=-m}^{m}p_iv_{-i}(x)=x. \]

Putting \(x=\gamma(p^0)\), we have

\[ 1-\sum p_i=1-\sum p_i\tilde v_{-i}(p^0)=\gamma(p^0)>0, \]

which contradicts the assumption. Thus \(v_i(\gamma)\) form a solution of the system (1) belonging to the domain \(U\). Now let \(v_i\) be an arbitrary solution of the system (1) from the domain \(U\). Put \(\gamma=1-\sum p_iv_{-i}\). It is easy to see that \(0<\gamma<1\) and \(F(\gamma)=0\). Hence \(v_i=v_i(\gamma)\).

Let \(\{v_i\}\in U\) be a solution of the system (1). Put \(v_{i_1\ldots i_k}=v_{i_1}\cdots v_{i_k}\) and define a function \(f(g)\) \((g\in G)\) by the formulas: \(f(e)=1\); \(f(g)=v_{-i_1\ldots -i_n}\), if \(v_{i_1}>v_{-i_1}\), or if \(v_{i_1}=v_{-i_1}\), \(i_1<0\);

\[ f(g)=\frac{2m-2}{m}\sum_{k=1}^{n-1} \frac{v_{-i_{k+1}\ldots -i_n}}{v_{i_1\ldots i_k}(2m-1)^k} +\frac{1}{m}v_{-i_1\ldots -i_n} +\frac{1}{m(2m-1)^{\,n-1}}\frac{1}{v_{i_1\ldots i_n}} \]

in the remaining cases (\(a_{i_1}\cdots a_{i_n}\) is a minimal representation of \(g\)). It is not hard to see that \(f\) is a nonconstant positive harmonic function. Therefore (see (1), p. 446) the random walk under consideration is transient.

1. Let \(G\) be a group with a finite number of generators. Suppose that the random walk on \(G\) is transient. Consider its trajectory \(x_1,x_2,\ldots,x_n,\ldots\) and choose, for each element \(x_n\), some minimal representation of it. With probability 1 the trajectory visits \(e\) only a finite number of times; therefore there is a number \(n_1\) such that the minimal representation of all \(x_n\) for \(n>n_1\) begins with one and the same generator \(a_{i_1}\). After time \(n_1\) the trajectory visits \(a_{i_1}\) only a finite number of times; therefore, starting from some time \(n_2\), the second generator \(a_{i_2}\) ceases to change, and so on. It is natural to call the infinite word \(\xi=a_{i_1},a_{i_2},\ldots\) a boundary point and to regard the sequence \(x_n\) as converging to \(\xi\). Infinite words (as well as finite ones) are subject to the natural identification following from the prescribed relations among the generators. In view of this identification, the limit of the sequence \(x_n\) does not depend on the choice of a minimal representation for the elements \(x_n\).

1. The Martin metric in the phase space \(E\) of an arbitrary irreducible countable Markov chain is given by the formula

\[ d(x,y)=\sum_{z\in E}\left|\frac{u(c,z)u(z,x)}{u(c,x)}-\frac{u(c,z)u(z,y)}{u(c,y)}\right|\lambda(z), \tag{2} \]

where \(c\) is some element of \(E\), \(\lambda(z)>0\), and \(\sum_{z\in E}\lambda(z)<\infty\). The phase space is completed with respect to this metric. The difference \(\Gamma\) between the completion of \(E\) and \(E\) is called the Martin boundary \((^1)\).

It is easy to show that, for a random walk on a free group with \(m\) generators, the Martin distance* between two sequences of elements tends to zero if and only if the number of generators that coincide at the beginning of the minimal representation of the elements of the sequences tends to infinity. It follows from this that the Martin boundary coincides with the boundary constructed in no. 4.

1. Theorem 3. The positive harmonic functions for a random walk on a free group with \(m\) generators are obtained by the formula:

\[ f(e)=\nu, \]

\[ f(a_{i_1}\ldots a_{i_n}) = \sum_{k=0}^{n-1} \mu_{i_1}^{-1}\ldots \mu_{i_k}^{-1} u_{-i_{k+1}}\ldots u_{-i_n} u_{i_1\ldots i_{k+1}} + u_{i_1}^{-1}u_{i_n}^{-1}\nu_{i_1\ldots i_n} \tag{3} \]

\[ (i_k+i_{k+1}\ne 0), \]

where

\[ \nu=\sum_{i=-m}^{m}\nu_i,\qquad \nu_{i_1\ldots i_{k-1}}=\sum_{i_k=-m}^{m}\nu_{i_1\ldots i_k}\ (k>1),\qquad \nu_{i_1\ldots i_k}\ge 0, \]

\[ \mu_i=\nu-\nu_i,\qquad \mu_{i_1\ldots i_k}=\nu_{i_1\ldots i_{k-1}}-\nu_{i_1\ldots i_k}\ (k>1). \]

Proof. According to (1), all positive harmonic functions are obtained by the formula

\[ f(x)=\int_\Gamma \lim_{y\to \xi}\frac{u(x,y)}{u(e,y)}\,\mu(d\xi), \tag{4} \]

where \(\mu\) is an arbitrary finite measure on the Borel subsets of the boundary \(\Gamma\). Each element \(\xi\) of \(\Gamma\) is uniquely written in the form \(a_{j_1}\ldots a_{j_k}\ldots\), where \(j_k+j_{k+1}\ne 0\) \((k=1,2,\ldots)\). Put \(\xi\in A_{i_1\ldots i_k}\) if, in this representation, \(j_1=i_1,\ldots,j_n=i_n\). Let \(B_{i_1}=\Gamma\setminus A_{i_1}\), \(B_{i_1\ldots i_k}=A_{i_1\ldots i_{k-1}}\setminus A_{i_1\ldots i_k}\).

Let \(x=a_{i_1}\ldots a_{i_n}\). Then the integrand in (4) is equal to \(\mu_{i_1}^{-1}\ldots \mu_{i_k}^{-1}u_{-i_{k+1}}\ldots u_{-i_n}\) on \(B_{i_1\ldots i_k}\) \((k=1,\ldots,n-1)\) and is equal to \(u_{i_1}^{-1}\ldots u_{i_n}^{-1}\) on \(A_{i_1\ldots i_n}\). Setting \(\nu=\mu(\Gamma)\), \(\nu_{i_1\ldots i_k}=\mu(A_{i_1\ldots i_k})\), we obtain (3).

Remark. Every group \(G\) with generators \(a_1,\ldots,a_m\) is isomorphic to a quotient group of the free group \(\widetilde G\) with the same generators by some normal divisor \(N\). The set of all harmonic functions on \(G\) is obtained if one considers harmonic functions on \(\widetilde G\) that are constant on the cosets of \(\widetilde G\) modulo \(N\).

Moscow State University
named after M. V. Lomonosov

Received
16 XI 1960

CITED LITERATURE

\(^1\) J. L. Doob, J. Math. and Mech., 8, 3, 433 (1959).
\(^2\) A. G. Kurosh, Group Theory, Moscow, 1953.

* In formula (2), \(c\) is taken to be the identity element \(e\) of the group.