Can there be a Diaconis-Shahshahani Upper Bound Lemma for Compact Groups?

Question

Let $G$ be a finite group and $\nu\in M_p(G)\subset \mathbb{C} G$ a probability measure on $G$ and let $\pi$ be the uniform distribution on $G$.

Denote by $d_\rho$ the dimension of a non-trivial irreducible unitary representation $\rho:G\rightarrow \operatorname{GL}(V_\rho)$ and define a map $\mathbb{C}G\rightarrow \operatorname{GL}(V_\rho)$ by:

$$\nu\mapsto \widehat{\nu}(\rho)=\sum_{t\in G}\nu(\delta_t)\rho(t).$$

Denote by $\operatorname{I}^*(G)$ a family of non-trivial, pairwise inequivalent irreducible unitary representations.

Denote by $\|\cdot\|_{\text{TV}}$ the total variation norm on $\mathbb{C} G$:

$$\|\mu\|_{\text{TV}}=\frac12 \|\mu\|_1=\frac12 \sum_{t\in G}|\mu(\delta_t)|.$$

The Upper Bound Lemma of Diaconis & Shahshahani states that:

$$\|\nu-\pi\|_{\text{TV}}^2\leq \frac14 \sum_{\rho\in\operatorname{I}^*(G)}d_\rho \operatorname{Tr}\left[\widehat{\nu}(\rho)^*\widehat{\nu}(\rho)\right].$$

This can be used to analyse the rate of convergence for random walks on finite groups. For example see my own MSc thesis.

Where $h$ is the Haar measure, can a similar formula for $\|\nu-h\|$ hold for compact groups? If yes, are you aware of a reference? If no, what are the barriers?

Similar here means a formula that uses a $\sum_{\operatorname{I}^*(G)}$. I expect that the problem is with the norm $\|\cdot\|_{\text{TV}}$.

Note that one of the benefits of using the total variation norm is that lower bounds are also available via:

$$\|\mu\|_{\text{TV}}\geq \frac12 |\mu(\phi)|,$$

for a test function $\phi\in F(G)$ such that $\|\phi\|_{\infty}\leq 1$.

In the 2-norm:

$$\|\mu\|_2=\sqrt{\sum_{t\in G}|\mu(\delta_t)|^2},$$ the upper bound lemma is actually an equation:

$$\|\nu-\pi\|_2=\sqrt{\sum_{\rho\in\operatorname{I}^*(G)}d_\rho \operatorname{Tr}\left[\widehat{\nu}(\rho)^*\widehat{\nu}(\rho)\right]}.$$

A Partial Answer:

There is a paper of Rosenthal (a student of Diaconis) where he states that

The previously mentioned finite-group methods appear to be applicable to compact groups.

The Diaconis-Shahshahani Upper Bound Lemma is one of these previously mentioned methods.

Revised Question:

Therefore the question is revised but is more difficult and also much softer in its scope:

What are major barriers to applying the Diaconis-Shahshahani Upper Bound Lemma to a random walk on a compact group?

Answer 1

I seem to be in a good position to answer this, so will give a try. I had the good fortune to work on the natural extension of Rosenthal's random walk on $SO(2n+1)$, namely the case where the rotation angle $\theta \neq \pi$. Even more luckily I got help from fellow graduate student at the time, Bob Hough, who contributed the critical insight that allowed us to finish the analogous upper bound in this paper. All details can be found in the latter.

The upper bound formula as obtained by Rosenthal is $$ \| \nu_t - \pi \|_\rm{TV}^2 \le \sum_{\mathbf{a} \neq (0,\ldots, 0) } d_{\mathbf{a}}^2 r_{\mathbf{a}}(\theta)^{2t}. $$ where $r_{\mathbf{a}}(\theta)$ is the so-called character ratio (i.e., character divided by dimension), which Rosenthal computed using Weyl character/dimension formula to be $$ r_{\mathbf{a}}(\theta) := \frac{\chi_{\mathbf{a}}( R(1,2;\theta))}{d_{\mathbf{a}}} = \frac{(2n-1)!}{\left(2 \sin \frac{\theta}{2}\right)^{2n-1}} \sum_{j=1}^n \frac{\sin (\tilde{a}_j \theta)}{\tilde{a}_j \prod_{r \neq j} \left(\tilde{a}_r^2 - \tilde{a}_j^2\right) }. $$ Here

• $R(1,2;\theta) = \left( \begin{array}{ccc} \cos \theta & -\sin \theta & \\ \sin \theta & \cos \theta &\\ & & I_{N-2} \end{array} \right) $, and can be replaced by any of its conjugate in $SO(2n+1)$.
• $\mathbf{a}$ is a sequence $n$ weakly increasing nonnegative integers, and $\tilde{a}_j = a_j + j -1/2$, i.e., $\mathbf{a} + (1/2,3/2,\ldots, n-1/2)$ is the corresponding highest weight vector (my convention is opposite of Macdonald's book, but consistent with Rosenthal's paper). The $\mathbf{a}$ so described index all the irreducible representations of $SO(2n+1)$, just as partitions of length $n$ index irreducible representations of $GL(n)$.

The goal is to show that each of $d_\mathbf{a}^2 r_\mathbf{a}(\theta)^2 = o(1)$, except for $\mathbf{a} = (0,\ldots, 0)$ corresponding to the 1-dimensional trivial representation. When $\theta = \pi$, the formula for $r_\mathbf{a}(\theta)$ can be bounded by taking absolute value of each summand. However when $\theta \neq \pi$ notice that the antecedent denominator $(2\sin \frac{\theta}{2})^{2n-1}$ increases exponentially in $n$, and the sum is highly oscillatory, making the absolute value bound too weak.

What Bob discovered is that the sum can be written as a contour integral, using the residue theorem. Thus one can appeal to saddle point techniques that are commonly used in estimating coefficients of various generating functions related to combinatorial or number theoretic quantities, such as the partition number or Stirling's formula.

Similar random walks on $SO(2n)$, $Sp(n)$ and with conjugacy classes with multiple angles of rotation "should" follow similar suit, though even for the single $\theta$ case it was already mind-blowingly tedious (to me at least).

In general I would say the barriers compared to discrete group conjugacy class walks are

• You have to control an infinite number of irreducible representations
• You need to bound values of Schur polynomials or their Laurent analogues on the unit circle in the complex plane, as opposed to characters of finite groups; this could be slightly less well developed since most people who are interested in bounding symmetric polynomials view them as real-valued functions. Also people like Diaconis and Aner Shalev and other random walk theorists are interested more in discrete setting, hence have spent a lot of energy developing bounds for symmetric characters $\chi^\lambda_\nu$.