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

and

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

and

The first is attained up to a factor of . The second is attained up to a factor of when is cyclic of order .

Advertisements

Like this:

LikeLoading...

Related

This entry was posted on Thursday, November 4th, 2010 at 11:08 pm and is filed under Diaconis book. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.