Let be a finite group and let . We define a probability distribution on by and for . Consider the random walk on starting at the identity where we step from to with probability . After steps, the probability that we are at is .
There are (at least) two reasonably efficient ways to find . One way is to use the Fourier Inversion Theorem and exploit the fact that the Fourier transform turns convolution into multiplication. An alternative, which bypasses the Fourier theory, is outlined below.
Let us `collapse’ the Markov chain given by so that we only keep track of whether we are at the identity, or at a non-identity element. The transition probabilities are shown in the diagram below. (For example, from a non-identity element, there is a unique group element that will take us to the identity; since , the transition probability from non-identity to identity is .)
The transition matrix for the collapsed chain is
The eigenvalues of are easily found: one must be , and the other is
Hence there exist constants such that
where is the probability that we are at the identity after steps. The constants are easily determined from the cases and : one finds that and .
Going back to the original problem, we argue that if the walker is at some non-identity state with probability then, by symmetry, the walker is at a particular with probability . Hence
for all , as claimed in the exercise. For the last part, we calculate that
where is the uniform distribution on . From the solution obtained by calculating Fourier coefficients we know that
The Upper Bound Lemma states that . Clearly this is the case here. (Note that if we take of order then we have equality for all .) The lower bounds of Exercise 5 become
The first is attained up to a factor of . The second is attained up to a factor of when is cyclic of order .