{'fraction_non_alphanumeric': 0.049786589563541234, 'fraction_numerical': 0.015420625086052596, 'mean_word_length': 3.5697747577702277, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Speed exponents of random walks on groups

For every 3/4<= beta<1 we construct a finitely generated group so that the expected distance of the simple random walk from its starting point is within a constant factor of n^beta. In fact, the speed can be set precisely to equal any nice prescribed function up to a constant factor.


Introduction
The central question in the theory of random walks on groups is how symmetries of the underlying space give rise to structure and rigidity of the random walks. For example, for nilpotent groups, it follows easily from bounds in Hebisch and Saloff-Coste (1993) that random walks have diffusive behavior, namely that the rate of escape, defined as the expected distance of the walk from the identity satisfies E|X n | ≍ n 1/2 .
(See also Thompson (2010) for more classes with this behavior.) On nonamenable groups, on the other hand, we have E|X n | ≍ n.
Starting with the works of Kesten (1959), the rate of escape has been connected to many other properties of the group, including the spectral radius, the volume growth, rate of entropy growth, and the Liouville property. More recently, Austin, Naor and Peres (2009) and Naor and Peres (2008) have established a beautiful connection between the rate of escape and embeddings of groups into Hilbert space, see (17).
The notation f ≍ g denotes that there exist constants c, C independent of n such that cf (n) ≤ g ≤ Cf (n). For what β is there a random walk on a group with E|X n | = n β+o(1) ?
The only known answers to this question were given by Erschler (1999), who realized that for a random walk on a group G satisfying E|X n | ≍ n β , the wreath product Z ≀ G has E|X n | ≍ n β+1 2 . Thus Erschler showed that the canonical random walk on the k − 1-times iterated wreath product of Z satisfies E|X n | ≍ n 1−2 −k .
The main goal of this paper is to show that in fact, all speed exponents between 3/4 and 1 are achievable in residually finite groups. In fact, we show much more: our groups allow us to adjust precisely E|X n | ≍ f (n) for a general class of functions f . For this, we use the permutation wreath product of Z and the action S of the so called piecewise mother groups M m on the boundary of their tree; see Section 6 for definitions.
Theorem 1. For any γ ∈ [3/4, 1) and any function f : R + → R + satisfying f (1) = 1 and the log-Lipshitz condition that for all real a, n ≥ 1 there is a bounded sequence (m ℓ ) such the random walk on Z ≀ S M m satisfies that with constants depending on γ only, E|X n | ≍ f (n).
For the theorem and throughout this paper, all random walks are symmetric and the step distribution has finite support. While the actual group construction for Theorem 1 is simple, the theory behind the analysis is more sophisticated and has many potential applications.
It is based on the analysis of permutation wreath products (see Section 4 for definitions).
Theorem 2. Let Y n be a random walk on a group Γ which acts on a set S. Fix o ∈ S,and let p n be the probability that the random walk o.Y n on S does not return to o in the first n steps. Assume that there is a constant c so that for all n ≥ 1 we have where the H term is the entropy of a random set called the inverted orbit. Let Λ be an infinite group and let λ(n) be the expected displacement for a generating random walk in Λ. Then the switch-walk-switch random walk X n on the permutation wreath product Λ ≀ S Γ satisfies E|X n | ≍ np n λ(1/p n ).
The main reason this theorem is useful is that it gives control of the expected displacement E|X n |, usually a difficult quantity, in terms of the function p n , which is often easier to compute. The condition (1) ensures that the action is significant enough to determine the speed of the switch-walk-switch random walk.
For a simple example, consider Γ = Z, with the free (Cayley) action. Then we are back to the ordinary wreath product, p n ≍ n −1/2 , and E|Y n | ≍ n 1/2 , and the entropy in (1) is of order log n. Repeated application of Theorem 2 then recovers the result of Erschler (1999).
Because of Theorem 2, understanding speed and entropy in wreath products can boil down to understanding return times of random walks on Schreier graphs, a much easier task.
Finally, we make this easier by constructing a family of Schreier graphs on which the random walk simply projects to nonnegative birth-and-death Markov chains. These are chains on the nonnegative integers where only nearest-neighbor moves allowed; the random walk there can be analyzed many ways, including electrical network theory. The corresponding action satisfies the condition (1), and Theorem 1 holds since p n can be adjusted sufficiently precisely (in fact to any function as specified in Theorem 1 with 3/4 replaced by 1/2.) Then by Theorem 2, the E|X n | can be determined up to a constant from the expected displacement in Λ for any infinite group Λ.
Our analysis is precise enough to give a quantitative improvement on Brieussel's theorem on entropy. In Brieussel (2011a) it is shown that entropy exponents between 1/2 and 1 are realizable; the same analysis can be extended to H(X n ) = f (n)n o(1) for a general class of functions f . Here we show that in fact the random walk entropy can also be adjusted much more precisely, up to a constant factor.
Theorem 3. For any γ ∈ [1/2, 1) and any function f : R + → R + satisfying f (1) = 1 and the log-Lipshitz condition that for all real a, n ≥ 1 and the implied constants depend on γ only.
The piecewise mother groups M m that we are using are related to those in the paper of Brieussel; the main difference is that our analysis is based on a careful geometric under-standing of the birth-and-death chain structure of the underlying Markov chains; also, it is key in our analysis of the speed to let Λ be an infinite group.
The groups M m are versions of automation groups. The most famous of such groups is the celebrated group of Grigorchuk (1984). The rate of escape on automaton groups was first studied by Bartholdi and Virág (2005), who used its sublinearity to show that the Basilica group is amenable. These results were extended to so-called degree zero automaton groups by Bartholdi, Kaimanovich and Nekrashevych (2010), and for degree one groups by Amir, Angel and Virág (2009). In Amir and Virág (2011), it was shown that degree three groups typically have linear rate of escape.
The idea to use permutational wreath product over these groups is due to Bartholdi and Erschler (2010); they used the Grigorchuk group as a base group to determine the exponent of the stretched exponential growth of its permutational wreath product; to  Brieussel (2011a) used the same groups we use to show that entropy exponents can freely vary between 1/2 and 1.
The permutational wreath product can be thought of as a relative of the usual wreath product Λ ≀ Γ, also known as the lamplighter product of Λ and γ. Thus we borrow terminology and think of Λ as the "lamp group" and of the switch-walk-switch walk as a type of Lamplighter walk. This analogy is limited though and must be used with care. For example, perhaps surprisingly, the lamplighter corresponding to a permutation wreath product does not light lamps along the random walk path o.Y n on the corresponding Schreier graph with root o. Instead, it lights the lamps along the inverted orbit o.Y −1 n , which may have a very different distribution (see Section 4).
The rest of the paper is built as follows: In Section 2, we analyze the distribution of the size of the inverted orbit. In Section 3 we give a precise version of the well-known inequality connecting random walk entropy and speed based on the bounds by Varopoulos and Carne. In Section 4, we define permutational wreath products and develop our bounds for speed and entropy in general permutational wreath products. In Section 5, we introduce and analyze the assembly line, a birth-and-death Markov chain which will be the basis of our construction; these are simpler to understand than the underlying groups. In Section 6 we introduce the underlying groups, prove specific estimates for the orbits in these groups and then apply the bounds of the previous sections to deduce the three main theorems. Finally, we close the paper with some open questions.

Random walks and inverted orbits
Let T i , i ∈ Z be a positive integer-valued i.i.d. sequence. The two sided-random walk with increments T i has value T 1 + . . . + T i for i ≥ 1 and −T −1 − . . . − T i for i < 0. Its image as i ranges over Z is a random set called the two-sided renewal process. Its gap distribution is the law of T i .
namely the times at which the inverted orbit visits the same point as at time t. Then V t has the same distribution as (t + ρ) ∩ [0, ∞) where ρ is the two-sided renewal process whose gap distribution is the law of the first return time of the Markov chain o.Y n .
Proof. Fix n. Let R ⊂ [1, t] and S ⊂ [1, n − t] be sets of integer times, and consider the We can write this event as the intersection of the events The equality in the first event can be written as Multiplying from the right by G 1 · · · G t−r we get Similarly, the equality in the second event is equivalent to Clearly, these specify the return times of two independent Markov chains. Such return times are renewal processes, and the gap distribution is given by the time of the first return. To verify our claim, all we have to check is that the first return time T for the walk with the inverse steps has the same distribution as that for the random walk with normal steps. Note and o.G −1 1 . . . G −1 ℓ = o, for all ℓ < k. If the first equality holds, then the second one is equivalent to Now, together with (2), this specifies the first return time for the walk with group increments in the reverse order: G k , . . . , G 1 .
Let Q n be the (random) occupation measure of the inverted orbit of the first n steps.
More precisely, for s ∈ S we have Q n (s) = n i=0 1(o.Y −1 i = s), the number of visits of the inverted orbit to s. We will often think of n as fixed and call Q n simply the inverted orbit.
The support of Q n is will be called the range. Let |Q n | denote the size of the range. Proof. Let B i the event that time i is the last visit to o.Y i up to time n. Note that by Proposition 4 P(B i ) = P(T > n − i). We have Changing variables with j = n − i we get so the last equality follows from the tail sum formula for expectation.
Corollary 6. Let T denote the first return time for the random walk o.Y n . Then for 0 ≤ t ≤ n we have Proof. By Proposition 4, we have where A, B are the number of renewals up to and including time t and n − t, respectively in two independent renewal processes with gap distribution given by the law of T . This gives the lower bound If A ≥ k/2, then the first k/2 gaps are all of size at most t ≤ n. So, by the independence of gaps, we can bound The same argument for B now concludes the proof.

Entropy and speed
Recall that the entropy of a finite non-negative measure µ supported on a countable set G is defined by where by convention 0 log 0 = 0. The entropy H(X) of a discrete random variable X is given by the entropy of its distribution; the entropy H(X 1 , . . . X n ) of several random variables is given by the entropy of the joint distribution of the X i . In order to define conditional entropy for two random variables X, Y , let f (y) denote the entropy of the conditional distribution of X given Y = y. Then the conditional entropy of X given Y is defined as H(X|Y ) := Ef (Y ).

The conditional entropy satisfies
A useful and easy fact is that among measures supported on a given finite set, the one having maximal entropy is the uniform measure on that set.
Let h(n) be the entropy of the n-step random walk in the group Λ. Recall that h is concave (Kaimanovich and Vershik (1983), Proposition 1.3) and hence by linear approximation we can extend it to a concave function on R + .
Lemma 7. For every n ≥ 1 the function x → xh(n/x) is concave.
Proof. By the concavity of entropy, we have The following is a precise version of the well-known relationship between entropy and expected distance (Erschler (2003)) that follows from the bounds of Varopoulos (1985) and Carne (1985).
Proposition 8. Consider a random walk X n on a weighted graph started at a vertex o, and let | · | denote graph distance from o. Then we have Proof. Let r ≥ 0 an integer. By leaving out nonnegative terms from the definition, we write By the bounds of Varopoulos (1985) and Carne (1985), Substituting this into (3) and then summing over v with |v| ≥ r we get For integer r > √ 2κn this gives Since q(r) is decreasing, this also holds for all real r > √ 2κn. Indeed, We now write and substitute r 0 = 2 nH(X n ) ∨ nκ, so that the numerator of the integrand is at least r 2 /2. This gives the upper bound Since η ≥ 1 and so κ = log(2 √ η) < η the claim follows.

Speed in permutation wreath products
We consider the following setup. Let Γ be a finitely generated countable infinite group acting on a set S. We single out an element o ∈ S and call it the root. Let µ be a finitely supported symmetric measure on Γ. Let Λ be a finitely generated countable (possibly finite) group.
The permutation wreath product Λ ≀ S Γ is the semidirect product of Λ S with Γ acting on it by permuting the coordinates. The multiplication rule, for ℓ, ℓ ′ ∈ (Λ S ) and g, g ′ ∈ Γ is where L is a random elemet of Λ chosen from a fixed symmetric finitely-supported measure.
We consider the random walk (called the switch-walk-switch random walk) on the permutation wreath product. Here the G i are independent choices from the measure on Γ, and the L i , L ′ i are independent choices from the measure on Λ. We have Keeping with the tradition for ordinary wreath products, we call the group Λ ≀ S Γ the Lamplighter group, and the above walk the lamplighter walk.
Unlike the usual lamplighter group, where there is a walker on the (Cayley) graph who keeps switching lights along its path, this walk cannot be interpreted as a lamplighter moving along the Schreier graph of the action G on S. This is because the switches happen at would be a Markovian random walk on the Schreier graph, but our case is different. Following Bartholdi and Erschler (2010) . . the inverted orbit of o under the walk Y n (or alternatively of the walk X n as they have the same action on S.) In particular, we get the useful observation, which will be exploited later, that the inverted orbit of X n depends only on Y n and not on the lamp group or the switch steps chosen.
A symmetric finitely-supported measure on a group defines a Cayley graph. Let |g| denote the corresponding graph distance of g from the identity.
With L i random walk increments on Λ as above, define A simple computation checks that both λ and λ are subadditive: Also, unlike the ordinary expected distance, both λ and λ are nondecreasing (by definition).
Lemma 4.1 in Lee and Peres (2009) implies that The following theorem connects speed on Λ to that on the permutation wreath product.
The main feature is that it only uses the tail of the first return time T of the random walk on the Schreier graph of (S, Γ). We emphasize that T relates to the ordinary random walk.
Theorem 9. The random walk X n on the permutation wreath product satisfies for n ≥ 1 for every p ≤ P(T > n).
Proof. Note that the number of switches of the light at s by time n given by for n ≥ 1. Sice all these lights have to be turned off to return to the identity, we have Let k be a constant whose value will be decided later on. Call an element s ∈ S thin if Q n (s) ≤ k, and call a time 0 ≤ t ≤ n thin if o.Y −1 t is thin. We can bound the right hand side below as E s∈S,s thin λ(Q n (s)).
Let N be the number of thin times. We want to bound the quantity in the expectation in terms of N. This gives the following minimization problem. Minimize λ(x i ) given that x i = N and the x i < k are nonnegative integers. Note that since λ is subadditive, we can decrease the quantity in question without violating the constraints if we replace two x i 's that are less than k/2 by their sum and zero. After repeating this procedure, we get that all but perhaps one of the nonzero x i are greater or equal than k/2. Let j be the number of substituting this into the above, we get by Corollary 6. Setting k = 2/p gives the lower bound of n/4, and substituting into (6) we get E|X n | ≥ npλ(1/p) 16 as claimed.
Analogous to Theorem 9 about speed, we have an upper bound for entropy in the wreath product. Again, the relation involves the return time of the random walk in the Schreier graph, since by Corollary 5 Theorem 10. We have H(X n ) ≤ H(Y n ) + H(supp Q n | |Q n |) + 2E|Q n | h n E|Q n | + log(n + 1) . and the expression on the right is increasing as a function of E|Q n |.
Proof. Write X n = (L n , Y n ), a pair containing a lamp configuration and a walk Y n on Γ.
We first consider the entropy of Q n .
≤ H(supp Q n | |Q n |) + H(|Q n |) + E|Q n | log(n + 1) the second inequality follows since 1 ≤ Q n (s) ≤ n + 1 for every s ∈ supp Q n . Further, the random variable |Q n | is between 1 and n + 1, so its entropy is at most log(n + 1).
We now turn to H(L n |Q n ). Note that given Q n , each entry of L n (s) is distributed as independent samples from a random walk on Λ of length Q n (s) ≤ 2Q n (s) (see (5)), which is at most now we use the monotonicity, concavity, and subadditivity of h (Kaimanovich and Vershik (1983) propositions 1.1 and 1.3) to get s h( Q n (s)) ≤ s 2h(Q n (s)) ≤ 2|Q n |h(n/|Q n |) By Lemma 7, we have that x → xh(n/x) is concave, so by Jensen's inequality H(L n |Q n ) ≤ 2E|Q n |h(n/E|Q n |).
Using |Q n | ≥ 1 the claimed inequality follows. Since the function x → xh(n/x) is concave and nonnegative, it must be increasing.
1. Given the size |Q n | of the support of Q n , the support can be described by a sequence of |Q n | elements from the ball B n (o) of radius n in the Schreier graph of (S, Γ). This gives H(supp Q n | |Q n |) ≤ E|Q n | log |B n (o)|.
However, as we will see in Section 5, for the groups we will be interested in one can give a better bound, linear in |Q n |.
2. If the lamp group Λ is finite, one may replace (7) by as every word in Λ can be described by log |Λ| bits.
The following lemma estimates the size of the inverted orbit of a random walk on a Schreier graph in terms of the speed of random walk on the permutation wreath product with Z 2 . Together with Theorem 13 it usually gives a better upper bound on the speed (of the random walk X n on Λ ≀ S G) than applying the Varopolous-Carne bound of Proposition 8 directly to the entropy bound of Theorem 10.
Lemma 12. Consider a random walk Y n on a Schreier graph S of a group G with inverted orbit Q n . Then Y n can be realized as the position of the lighter in the switch-walk-switch random walk X ′ n on the permutation wreath product Z 2 ≀ S G. There exists a word in G that is equivalent to Y n whose inverted orbit includes supp Q n , and whose expected length is at most 3E|X ′ n |.
Proof. Note that given Q n , each lamp in supp Q n is turned on or off with probability half each, independently.
If L ′ n is the lamp configuration at time n, then given Q n , the distribution of L ′ n and the inverted configuration L ′′ n defined as is the same. Let X ′′ n = (L ′′ n , Y n ). By the above, X ′′ n has the same distribution as X ′ n . Since in X ′ n all the lamps in L ′ n are turned on, there is a word W ′ of length at most |X ′ n |, equivalent to X ′ n , whose inverted orbit includes supp L ′ n . Similarly, there is a word W ′′ of length at most |X ′′ n | whose inverted orbit includes supp L ′′ n . Then the inverted orbit of the word W ′′ W ′′ −1 W ′ contains supp Q n , it is equivalent to X ′ n and its expected word length is at most Theorem 13. For every q ≥ E|Q n | we have E|X n | ≤ 3λ (n/q) q + 12 √ n H(Y n ) + H(supp Q n ) + E|Q n |.
Proof. We have |X n | ≤ A + B, where A is the length of the shortest word equivalent to Y n whose inverted orbit contains supp Q n and B is the number of lamp steps required to turn off the lamps.
We first bound B. Given Q n , the expected number of lamp moves required to turn off the lamps is bounded above by first we use the monotonicity of λ to round up each argument to the next integer multiple of k = n/q. The total sum of the new arguments is at most the total sum of the originals ones (i.e. 2n) plus |Q n |k. Then we use subadditivity to bound the sum by Taking expectations we get EB ≤ λ (n/q) 3q.
Regarding A, Lemma 12 gives us where X ′ n is the switch-walk-switch random walk on Z 2 ≀ S G. For this, we use the entropy bound (9) and the Varopoulos-Carne bounds in Proposition 8 to get This completes the proof.
We summarize the results of this section and deduce some conclusions using the Varopoulos-
Now for a generating random walk on any transitive graph λ(n) ≥ c √ n, see Lee and Peres (2009). The upper bound follows.

The assembly line
The goal of this section is to describe an analyze a simple birth-and-death Markov chain, called the assembly line, which is the core of our construction. In the next section, we will show that it essentially a Schreier graph of a group. However, the first part of the analysis does not need this fact. Fortunately, this walk projects to a birth-and-death Markov chain. Indeed, consider the projection from S to the set of finite binary strings . . . w 3 w 2 w 1 → . . . w 3 w 2 w 1 , w i = 1(w i > 0).
The projection of the walk has the same description as above, except that "randomize" for the w i means Note also that from each w ∈ S, there are only two possible new positions one can move to (except o, where there is only one). This implies that the graph structure of this walk is that of the nearest-neighbor graph of natural numbers. Indeed, the structure is a standard Gray code -an ordering of all binary strings so that consecutive strings differ by only one bit.
It is easy to that the position of a given string in this order is where the last sum has only finitely many nonzero terms.
Thinking of the walk on S as a random walk on a weighted graph, the uniform stationary measure on S projects to a stationary measure on S. More precisely, and the edge weights are within constants of the vertex weights. This automatically gives that the resistance between o and 2 n in S satisfies where r ℓ is the sum of the inverse vertex weights for vertices between these two positions, and m * is the maximum degree. That is, since the sum factorizes. In short, Define v ℓ = m 1 · · · m ℓ . Note that the ball of radius 2 ℓ in S about o contains exactly v ℓ vertices.
Proof. We truncate the graph at 2 ℓ , and consider the random walk on the truncated graph together with the random walk on the original graph. These are naturally coupled until the hitting time τ of 2 ℓ . Let T ′ denote the first return time in the truncated graph. Then we have So we have (by bounding the i = 0 case by 1) The sum of the first quantities equals ET ′ = v ℓ (since in any connected weighted graph the expected return time to a vertex equals the total volume over the weight of the vertex). Also P(T > τ ) = 1/R(0, 2 n ) ≤ 1/r ℓ . The claim follows if we set n = v ℓ r ℓ .
Lemma 16. Let X be nonnegative interger-valued random variable with expectation a sat-

Proof. By Markov's inequality for all integers t we have
Proof. This is a birth-and-death chain, one of the simplest kind of Markov chains, and the expected hitting times can be computed explicitly. By Levin, Peres and Wilmer (2009) (page 27, formula (2.16)), we have Proof. We have walk hits 2 ℓ before o and T * > t ⇒ T > t, where T * is the time to hit o after the first time of hitting 2 ℓ . The probability of the first event is given by 1/R(0, 2 l ) ≥ 1/(r ℓ 2m * ) by (12). We now consider T * > t. Note that T * stochastically dominates the hitting time T ′ from 2 l to o in the graph truncated at 2 l . This is because we T * = T ′ + T ′′ where T ′′ is the number of steps outside [0, 2 ℓ ] before hitting 0. Note that T ′ also stochastically dominates the hitting times of o in the truncated graph when starting from lower vertices. Thus Lemma 16 gives P(T ′ > ET ′ /4) ≥ 1/31.
We express the results of Propositions 15 and 18 in terms of n.
The combination implies a matching upper bound on (14) and lower bound on (15) up to a constant factor depending on m * only.
For the upper bound, we have We finish this subsection by showing that one can get good control over the sequence {α n } by choosing the appropriate degree sequence {m i }.
Lemma 20. For any γ ∈ [1/2, 1) and any function f : R + → R + satisfying f (1) = 1 and the log-Lipshitz condition that for all real a, n ≥ 1 there is a bounded sequence (m ℓ ) such that for all n ≥ 1 we have Proof. Note that By the assumptions on f we have Set m * be the smallest integer m ℓ+1 so that the upper bound at is not more than 1. This depends on γ only. Now, for ℓ ≥ 1 inductively choose then (16) and induction give the inequality which holds trivially for ℓ = 0.
Equivalently, by definition of α n , the inequality holds at the values n = n ℓ .
To get the claim for all integers, recall that n αn = v l(n) is constant between n ℓ and n ℓ+1 while f is increasing and may change by a factor at most m * between n ℓ and n ℓ+1 , so for all For the value of c γ note that the right hand side of (16) is at most one when m ℓ+1 ≥ e × e 1/(1−γ) , and ⌈e × e 1/(1−γ) ⌉ ≤ 3e 1/(1−γ) .

The piecewise mother groups
The Markov chain random walk on the "assembly line" introduced in Section 5 is a random walk on a Schreier graph of a certain group that we will now introduce.
Given a sequence m = {m i } i≥1 of integers m i ≥ 2, we define T m , the spherically symmetric rooted tree with degree sequence m to be the following graph. The vertex set given by finite sequences a k · · · a 1 where a i ∈ {0, . . . , m i − 1}, where the empty sequence o is the root. The edge set consists of all pairs of vertices of the form {a k · · · a 1 , a k−1 · · · a 1 }.
Let Aut(T m ) be the set of rooted automorphisms of T m , i.e. automorphisms fixing the root. The groups M m will be subgroups of Aut(T m ).
Thus the γ i are elements of Aut(T τ m ) where T τ m is the tree with the shifted degree sequence τ m := m 2 , m 3 , . . .. The natural action of the group Aut(T m ) on infinite strings (the boundary of the tree) · · · a 3 a 2 a 1 can be defined recursively by · · · a 3 a 2 a 1 .γ = (· · · a 3 a 2 .γ a 1 )a 1 .σ More generally, any automorphism can be written as a product of automorphisms γ v of subtrees of vertices v at level ℓ and a permutation permuting vertices at level ℓ. The γ v are uniquely determined and are called the sections of γ at v.
We will be interested in two special types of automorphisms: 1. Permutations: automorphisms of the form σ = id, id, . . . , id σ which simply permute the children of the root according to σ, with all other sections trivial.
2. Propagating actions: For every ℓ ≥ 1 fix some permutation σ ℓ ∈ Sym(m ℓ ). Then we define recursively a ℓ = a ℓ+1 , σ ℓ+1 , · · · , σ ℓ+1 id A simple example is when H is the set of all propagating actions where σ ℓ depends only on m ℓ ; in the rest of the paper we will assume that this is the case; this choice affects only the constants in our bounds.
We define M m as the group generated by the propagating actions H and the permutations Sym(m).
We consider the random walk Y n on M m where the step distribution is the even mixture of uniform measures on Sym(m 1 ) and H. By definition of H, the random walk o.Y n on infinite strings (with finitely many nonzero letters) corresponds to the assembly line walk introduced in Section 5.
Before going on to prove an upper bound on the entropy of the walk X n (which will then translate to a bound on the speed of X n ), we must further analyze some structures related to the inverted orbit.
n is a sequence of rays in the tree T m . Their union is a subtree of T m called the ray tree. Each ray in the ray tree ends with an infinite sequence of zeros.
Lemma 21. If a vertex v has exactly one child wv in the ray tree then the section at wv is just a propagating action, and the set of descendants of wv in the ray tree is just the 0-ray from wv.
Proof. Let |v| denote the distance of v from o in the graph metric. Consider the section at v of the word Y n , written in alternating form s v = σ 1 a 1 σ 2 a 2 σ 3 a 3 ..σ k , where σ i ∈ Sym(m |v|+1 ) and the a i are propagating actions in the descendant subtree of v.
Since v has only one child wv in the ray tree, we have This implies that 0.d 2 = 0.d 3 = 0.d k−1 = 0, so the section at wv is just a 1 a 2 a 3 ..a k−1 , a propagating action. The set of descendants of v in the ray tree is exactly the union of rays i.e. the ray · · · 0000wv, as required.
We can now show the following claim: Lemma 22. The number of ray trees with with r infinite rays is at most (m * + 1) 6r .
Proof. Prune the ray tree at each ray after the first lone child. In other words, if v is the first vertex in a ray to have only one child u in the ray tree, then u is in the pruned tree but its descendants are not. Note that the pruned tree determines the ray tree: the ray tree is given by adding 0-rays to the leaves of the pruned tree.
The pruned tree is finite; let i be the number of its vertices. Since we pruned each ray at the first lone child, any vertex in the pruned tree save for the leaves and their parents has at least two children. If the total number of leaves is r, then the total number of children is at least r + (i − 2r) * 2, we get the inequality i ≤ 3r − 1.
The tree can be described by a path that visits every vertex and passes through every edge at most twice; such a path can be described by 2i numbers between 0 and m * giving a list of directions which neighbor to go to next. The number of such lists is at most (m * + 1) 6r .
Lemma 23. The number of group elements for which there are words with a given ray tree with r rays is at most (m * !) 3m 2 * r .
Proof. For a group element g its section at a vertex determines all the sections on the descendant of the vertex. Define the reduced section at a vertex v as the permutation part of the section a in its decomposition a = a i σ.
A finite rooted subtree of T m is called full if each vertex either has maximal number of children or no child.
Given a rooted full subtree of T m , the sections of g at the leaves together with the reduced sections at the rest of the subtree determine the action of g on T m . Now given a word, consider the pruned version T ′ of its ray tree. Let T ′′ be the smallest full subtree of T m containing T ′ . This is called the minimal tree in Brieussel (2011a).
By Lemma 21 the sections at the leaves of T ′′ are either permutations or propagating actions. The number of vertices of T ′′ is at most m * times the number of vertices in T ′ , which is at most 3r by Lemma 22.
The total number of permutations together with propagating actions is bounded above by m * ! + 2!3! · · · m * ! ≤ (m * !) m * . So the total number of elements for which there is a word with a given ray tree is bounded above by (m * !) 3m 2 * r .
The next proposition contains an upper bound on the entropy of the walk on M m . The same bound with a multiplicative error term of n o(1) was first proved by Brieussel (2011a) using techniques from .
We take a different approach, describing an element Y n through the inverted orbit of the random walk word and the sections of Y n .
This is similar to the approach in Brieussel (2011a), where a slightly different tree is used to describe a word. The ray-tree description of the inverted orbit together with our tight estimates on the expected size of the inverted orbit allow us to get a tighter bound.
Proof. The conditional entropy is the expected entropy of the conditional distribution. However, the ray-tree is determines the support of Q n , and it has |Q n | infinite rays. Thus the conditional distribution of supp |Q n | given |Q n | is supported on a set of size at most (m * + 1) 6|Qn| . The entropy of the conditional distribution is bounded by the logarithm of this. The first claim follows by taking expectations, and the second follows by the trivial upper bound H(|Q n |) ≤ log(n + 1).
For the second claim, note that the number of group elements with a word with a given ray tree with r leaves is at most (m * !) 3m 2 * r by Lemma 23, so multiplying by the number of r-trees and taking logarithms gives the bound. We used the inequality 6 log(m * +1)+3m 2 * log(m * !) ≤ 5m 3 * log m * . For the last inequality, use the conditional entropy formula and the fact that 1 ≤ |Q n | ≤ n + 1, so H(|Q n |) ≤ log(n + 1).
By Lee and Peres (2009), for an infinite group, λ(n) is at least a c √ n. In particular, in the second inequality, the first term is dominant. Thus our bounds are tight up to constant factor, since by (4) we have λ ≤ c ′ λ.
Combining these inequalities yields the Theorem.
Denote h 1 the entropy of the step distribution. Another lower bound, useful for finite or small lamp groups is Proof. By Corollary 14 for every p ≤ P(T > n) and for every q ≥ n i=0 P(T > i) we have H(X n ) ≥ np 2 λ 2 (1/p) 4096 , H(X n ) ≤ H(Y n ) + H(supp Q n | |Q n |) + 2q (h (n/q) + log(n + 1)) .
The first two inequalities follow just as in Theorem 25. For the last inequality, note that for X n = (L n , Y n ) we have H(X n ) ≥ H(L n |Q n ) ≥ h 1 EQ n where we used the monotonicity of entropy.
Proof of Theorems 1 and 3. Theorem 3 follows directly from Lemma 20 and Theorem 26 for finite lamp groups, since h(·) in this case is bounded by a constant.
For Theorem 1, we could use Theorem 2, but in this case there are more direct arguments.
Note that given such f ,f (n) = f 2 (n)/n satisfies the conditions of Lemma 20. The theorem now follows from Theorem 25, and the fact that simple random walk on Z satisfies 2 π √ k ≤ λ(k) = λ(k) ≤ √ k.
Remark 27. By following the constants throughout the theorems, we get the following explicit constants for the bounds speed and entropy of the groups constructed in the main theorems. Recalling that in lemma 20 one may take m * ≤ C γ = 3e 1 1−γ . For Theorem 3 we get log 2 1000C 3 γ f (n) ≤ H(X n ) ≤ 16C 9/2 γ f (n) and for Theorem 1: 1 2γ−1 f (n) The constants can be improved by a more careful calculation. There are also other points in the proof were more careful choices would improve the constants, such as choosing a different set of generators for the base group and noticing the groups constructed actually have a degree sequence consisting of 2 and m * only.

Open questions
First, it would be nice to get the missing exponents; let us conjecture a positive answer to the question of Vershik and Peres: Conjecture 28. For every β ∈ (1/2, 3/4) there exists a random walk on a finitely generated group with E|X n | ≍ n β .
It is also interesting what exponents one can get for finitely presented groups, of which there are only countably many. We believe that our examples can be modified to get a dense set of exponents in [3/4, 1], but not to make the exponents oscillate. In this more restricted world, the following is still open.
Question 29. Let X n be a random walk on a finitely presented group. Is there necessarily a β so that E|X n | = n β+o(1) ?
Related to this, we also have Conjecture 30. The set of β so that there exists a finitely presented group and a random walk on the group so that E|X n | = n β+o(1) is dense in [1/2, 1].
The Hilbert compression exponent α * (G) of a group of G is the supremum over all α ≥ 0 such that there exists a 1-Lipschitz mapping f : G → L 2 and a constant c > 0 such that for all x, y ∈ G we have f (x) − f (y) 2 ≥ cdist(x, y) α . Austin, Naor and Peres (2009) showed that the speed exponent β(G), if exists, satisfies α(G)β(G) ≤ 2. The groups we are considering are permutation wreath products by piecewise automaton groups. It is still an open question to give the precise speed, or even entropy exponent on any of the classical automaton groups (except perhaps the lamplighter group); we will skip the definition of these groups but they can be found in, for example Amir et al. (2009).
Problem 32. Specify the speed exponent or the entropy exponent in any of the following groups: Grigorchuk's group, Basilica group, Hanoi towers group, degree-zero mother groups.