Let G be a finite group and E a generating set for G. Let P be a probability measure on G whose support is E. We define a random walk on G as follows. At the zeroth stage, we set w 0 =1. At the k th stage, we set w k =w k&1 x, where x # E is chosen with probability P(x). For g # G, the probability that w k = g is given by P* k (g), where P* k denotes the k-fold convolution power. We are interested in when, and more importantly, how fast P* k converges to the uniform distribution U on G.
Character theory of finite groups is directly relevant in the important special case that E is a union of conjugacy classes and P is constant on conjugacy classes. In this case we let P = g # G P( g) g # Z(C[G]). Then P* k converges to U if and only if P k converges to the primitive central idempotent e 1 =|G| &1 g # G g. Using the familiar central characters | / : Z(C[G]) ร C defined for each / # Irr(G) by | / (z)=/(z)ร/(1), one sees that P k converges to e 1 if and only if no nonprincipal degree one character of G is constant on E. Character theory is indirectly relevant even when E is not a union of conjugacy classes, since the rate of convergence for a random walk based on E can be compared to the rate for another set F which is a union of conjugacy classes; see [4]. From now on we assume that E is a union of conjugacy classes and P is constant on conjugacy classes.
It was shown in [5] that near-uniformity is achieved in n log n steps when G=S n and E is the set of all transpositions in G (actually ``parity problems'' require that the identity be included in E). This has an important analog when G is a finite classical group over GF(q) of rank n, with natural module V. We fix a positive integer d and require that E consist of elements x such that dim V(x&1) is at most d. We want to show that near-uniformity is achieved in O(n) steps, where the implied constant depends only on d and q. Repeated use of the relation V(xy&1)/ V(x&1) y+V( y&1) shows that at least O(n) steps are needed. When G=SL(n+1, q) and E is the set of all transvections in G, Hildebrand [10] article no. AI961635 46