## 3B Exercise 6: Upper bound lemma

Let $G$ be a finite group and let $\varepsilon > 0$. We define a probability distribution $P$ on $G$ by $P(\mathrm{id}) = 1 - \varepsilon/2$ and $P(s) = \varepsilon\bigl/2(|G|-1)$ for $s \not= \mathrm{id}$. Consider the random walk on $G$ starting at the identity where we step from $t$ to $st$ with probability $P(s)$. After $k$ steps, the probability that we are at $t \in G$ is $P^{\star k}(t)$.

There are (at least) two reasonably efficient ways to find $P^{\star k}$. 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 $P$ 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 $s$ that will take us to the identity; since $s \not= \mathrm{id}$, the transition probability from non-identity to identity is $\varepsilon\bigl/2(|G|-1)$.)

The transition matrix for the collapsed chain is

$A = \left( \begin{matrix} 1 - \varepsilon /2 & \varepsilon /2 \\ \varepsilon\bigl/2(|G|-1) & 1 - \varepsilon\bigl/2(|G|-1) \end{matrix} \right)$

The eigenvalues of $A$ are easily found: one must be $1$, and the other is

$\lambda = \mathrm{Tr}\ Q - 1 = 1 - \frac{\varepsilon|G|}{2(|G|-1)}.$

Hence there exist constants $a,b \in \mathbf{R}$ such that

$p_k = a + \lambda^k b$

where $p_k$ is the probability that we are at the identity after $k$ steps. The constants are easily determined from the cases $k=0$ and $k=1$: one finds that $a= 1/|G|$ and $b = (|G|-1)/|G|$.

Going back to the original problem, we argue that if the walker is at some non-identity state with probability $q$ then, by symmetry, the walker is at a particular $s \in G \backslash \{\mathrm{id}\}$ with probability $q/(|G|-1)$. Hence

$P^{\star k}(\mathrm{id}) = \frac{1}{|G|} + \frac{|G|-1}{|G|} \lambda^k$

and

$P^{\star k}(s) = \frac{1}{|G|} - \frac{1}{|G|} \lambda^k$

for all $s \in G$, as claimed in the exercise. For the last part, we calculate that

$||P^{\star k} - U|| = \frac{1}{2} \sum_{s \in G} \Bigl| P^{\star k}(s) - \frac{1}{|G} \Bigr| = \frac{|G|-1}{|G|} \lambda^{k}$

where $U$ is the uniform distribution on $G$. From the solution obtained by calculating Fourier coefficients we know that

$T_k = \sum^\star_{\rho} d_\rho \mathrm{Tr}( \hat{P}(\rho)^k {\hat{P}(\rho)^k}^\star) = (|G| - 1) \lambda^{2k}.$

The Upper Bound Lemma states that $||P^{\star k} - U||^2 \le T_k/4$. Clearly this is the case here. (Note that if we take $G$ of order $2$ then we have equality for all $k$.) The lower bounds of Exercise 5 become

$\frac{|G|-1}{|G|} \lambda^k = ||P^{\star k} - U || \ge \frac{T_k}{2|G|} = \frac{|G|-1}{2|G|} \lambda^{2k}.$

and

$\Bigl( \frac{|G|-1}{|G|} \lambda^k \Bigr)^2 = ||P^{\star k} - U ||^2 \ge \frac{T_k}{4|G|} = \frac{|G|-1}{4|G|} \lambda^{2k}.$

The first is attained up to a factor of $\lambda^k/2$. The second is attained up to a factor of $1/2$ when $G$ is cyclic of order $2$.