This section begins with a simple question apparently unrelated to representation theory:
How many times should we shuffle a deck of cards in order to randomize it?
Obviously there are some details to be addressed, namely a way to quantify “randomize,”” but also developing a procedure to model the dynamics of repeated card shuffling. This latter problem will be addressed with a newly introduced sort of multiplication—convolutions—in which shuffling is the act of taking repeated powers of a fixed probability on the symmetric group. We shall use representation theory to establish a notion of Fourier transform that (as usual, for those who have encountered the concept in differential equations or waves course) turns the complicated analysis of convolutions into straightforward multiplication.
This Fourier theory is useful and interesting for its own reasons, and connects nicely to our previous material, so we begin by mentioning the fundamentals of its construction.
9.1 Fourier Transform
Introduction
In this section we more systematically study the operators \(\hat{f}(\rho)\) introduced in Lemma 8.1, where \(f \in \mathscr{L}^{2}({G})\), \(\rho: G \to \operatorname{GL}(V)\) is a representation, and \[
\hat{f}(\rho) \coloneqq \sum_{h \in G} f(h) \rho(h) \in \operatorname{End}(V).
\] For reasons that will become clearer throughout our discussion, we call \(\hat{f}(\rho)\) the Fourier transform of \(f\) at \(\rho\)—though we do not assume the reader is familiar with Fourier theory (even in more commonly used incarnations of this term) before coming to this section. Notice that the language here is hinting that we can learn things about \(f\) by evaluating this sort of weighted averaging process at different representations of \(G\).
Consider further that the Reynolds operator (Exercise D.5, Theorem 5.2), which was instrumental in our development of character orthogonality, can be understood in this language:
Remark 9.1 (Theorem 5.2). Let \(G\) be a finite group and fix some representation \(\rho: G \to \operatorname{GL}(V)\). Then the Fourier transform at \(\rho\) of the constant function \(U: G \to [0,1]\) given by \(U(g) = \frac{1}{|G|}\) is the orthogonal projection onto the invariant subspace \(V^G\) with respect to the \(G\)-invariant inner product: \[
\hat{U}(\rho) = \frac{1}{|G|} \sum_{h \in G} \rho(h): V \twoheadrightarrow V^G.
\]
Recall that this Theorem served as a starting point for character theory, in particular the orthogonality of characters, which hints at the power of our emerging framework.
Remark 9.2. Throughout this section, as above, we will identify functions \(G \to [0,1]\) with functions \(G \to \mathbb{C}\) under the natural inclusion \([0,1] \hookrightarrow\mathbb{C}\).
First we establish a result on how Fourier transforms interacts with decompositions of representations (recall the proof of Theorem 8.1):
Proposition 9.1 If \(\rho: G \to \operatorname{GL}(V)\) and \(\sigma: G \to \operatorname{GL}(W)\) are representations, then \[
\hat{f}(\rho \oplus \sigma) = \hat{f}(\rho) \oplus \hat{f}(\sigma)
\] for all \(f \in \mathscr{L}^{2}({G})\). In particular, knowing the Fourier transform of \(f\) at every irreducible representation of \(G\) allows us to deduce the transform at any other representation.
Suppose that we have enumerated representatives for each irreducible representation of \(G\), say \(\rho_i: G \to \operatorname{GL}(V_i)\) for \(1 \leq i \leq r\), and consider the following:
Definition 9.1 Fix a finite group (G), and let \[
\rho_i : G \to \operatorname{GL}(V_i), \qquad 1 \le i \le r,
\] be representatives of the isomorphism classes of irreducible representations of \(G\). The Fourier transform of \(f\) is \[
\begin{aligned}
\mathscr{F}: \mathscr{L}^{2}({G}) & \to \operatorname{End}(V_1) \oplus \cdots \oplus \operatorname{End}(V_r) \\
f & \mapsto \mathscr{F}(f) = \left( \hat{f}(\rho_1),\dots,\hat{f}(\rho_r) \right).
\end{aligned}
\]
This name is appropriate in the sense that any other Fourier transform \(\hat{f}(\rho)\) can be deduced from the data of \(\mathscr{F}(f)\). Notice that domain and codomain of \(\mathscr{F}\) are the same dimension, as we have established the identity \[
|G| = (\dim V_1)^2 + \cdots + (\dim V_r)^2.
\] As we will see, this correspondence is actually an isomorphism of vector spaces; even more, it is an isomorphism of algebras once we think a bit more carefully about which multiplication laws we should equip these spaces with. The Fourier transform certainly does not turn pointwise multiplication of functions into the composition of linear operators, as we can see from the following examples.
Example 9.1 Recall that \(\mathbb{Z}/{n}\mathbb{Z}\) has \(n\) distinct irreducible representations. We have written these as \(U_{k,n} = \mathbb{C}\) for \(0 \leq k < n\), where \(1 \in \mathbb{Z}/{n}\mathbb{Z}\) acts on \(z \in U_{k,n}\) by \[
z \mapsto e^{\tfrac{2\pi k}{n} i} z,
\] i.e., rotating the plane by \(\tfrac{2\pi k}{n}\) radians. Given a function \(f: \mathbb{Z}/{n}\mathbb{Z} \to \mathbb{C}\), the Fourier transform associates to \(f\) an \(n\)-tuple \(\mathscr{F}(f) = (a_0,\dots,a_{n-1})\) of complex numbers via \[
a_k = \sum_{j=0}^{n-1} f(j) e^{\tfrac{2\pi k j}{n} i} = \sum_{j=0}^{n-1} f(j) \zeta^{k j},
\] where \(\zeta = e^{\tfrac{2\pi}{n} i}\) is a primitive \(n\)-th root of unity. This is known as the discrete Fourier transform, though beware that many authors use other conventions in defining this process: for example, dividing through by \(n\) or re-indexing our \(k\) as \(n-k\) so that this process is more directly connected to decomposing \(f\) into the basis of characters. In our case, we can recover \(f\) from the coefficients as follows: \[
f(j) = \frac{1}{n} \sum_{k=0}^{n-1} a_k \zeta^{-kj},
\tag{9.1}\] In particular, this means the discrete Fourier transform is an isomorphism (since it is invertible). Also note that these coefficients measure interesting properties, especially if we think of \(f\) as an \(n\)-periodic function \(\mathbb{Z}\to \mathbb{C}\). For example, \(n a_0\) is exactly the average value of \(f\).
Example 9.2 Consider the function \(f \in \mathscr{L}^{2}({\mathcal{S}_{3}})\) given by \[
\begin{gathered}
f(\mathbb{I}) = \tfrac{1}{4}, \quad f((1\ 2)) = f((2\ 3)) = \tfrac{1}{8}, \quad \text{ and } \\
f((1\ 3)) = f((1\ 2\ 3)) = f((1\ 3\ 2)) = \tfrac{1}{6}.
\end{gathered}
\] Take the basis \(\{e_1-e_2,e_2-e_3\}\) for the standard representation as in Example 4.20, we compute the transforms (either by hand or Listing 9.1).
Listing 9.1: Computing the Fourier transform of a function
G = SymmetricGroup(3)f = { G(()): 1/4, G((1,2)): 1/8, G((2,3)): 1/8, G((1,3)): 1/6, G((1,2,3)): 1/6, G((1,3,2)): 1/6}rho_triv = {g: 1for g in G}rho_sgn = {g: g.sign() for g in G}A = matrix([[-1, 1], [0, 1]])B = matrix([[0, -1], [1, -1]])rho_std = { G(()): A^0, G((1,2)): A, G((1,2,3)): B, G((1,3,2)): B^2, # Since (1,2,3)(1,2,3) = (1,3,2) G((2,3)): A*B, # Since (1,2)(1,2,3) = (2,3) G((1,3)): A*B^2# Since (1,2)(1,3,2) = (1,3)}def fourier_transform_at(func, rep): f_hat =0for h in G: f_hat += func[h] * rep[h]return f_hat# Calculate the components of the Fourier transformhat_f_triv = fourier_transform_at(f, rho_triv)hat_f_sgn = fourier_transform_at(f, rho_sgn)hat_f_std = fourier_transform_at(f, rho_std)# Display the resultsprint("Fourier Transform at trivial rep:")show(hat_f_triv)print("\nFourier Transform at alternating rep:")show(hat_f_sgn)print("\nFourier Transform at standard rep:")show(hat_f_std)
Regardless of our approach, we find that \[
\mathscr{F}(f) = \left(1,\tfrac{1}{6}, \tfrac{1}{24} \begin{psmallmatrix}
2 & -1 \\
-1 & 2
\end{psmallmatrix} \right).
\] It is less clear from this example that the Fourier transform on \(\mathscr{L}^{2}({\mathcal{S}_{3}})\) is invertible.
Theorem 9.1 (Fourier inversion) The Fourier transform is a vector space isomorphism. In particular, there is an inverse transform given by \[
\begin{aligned}
\mathscr{F}^{-1}: \operatorname{End}(V_1) \oplus \cdots \oplus \operatorname{End}(V_r) & \to \mathscr{L}^{2}({G}) \\
T_1 + \dots + T_r & \mapsto \left( g \mapsto \frac{1}{|G|} \sum_{i=1}^r \dim V_i \operatorname{Tr}\left( \rho_i(g^{-1}) T_i \right) \right).
\end{aligned}
\tag{9.2}\]
Proof. We have already seen that the domain and codomain of \(\mathscr{F}\) have the same dimension, so it suffices to exhibit a left inverse, i.e., that \(f\) can be recovered from the data of its Fourier transform. We will show that \(\mathscr{F}^{-1} (\mathscr{F}(f)) = f\), which unpacks to \[
f(h) = \frac{1}{|G|} \sum_{i=1}^r \dim V_i \operatorname{Tr}\left( \rho_i(h^{-1}) \hat{f}(\rho_i) \right)
\] for all \(h \in G\). Since \(\mathscr{F}\) is linear, it is enough to prove this formula holds for the elements of a given basis of \(\mathscr{L}^{2}({G})\). We will consider the indicator functions \(\mathbb{1}_{\{g\}}: G \to \mathbb{C}\) (recall Exercise G.5) Note that \[
\widehat{\mathbb{1}_{\{g\}}}(\rho) = \sum_{h \in G} \mathbb{1}_{\{g\}}(h) \rho(h) = \rho(g)
\] for any \(\rho\), so the right hand side of the inversion formula is: \[
\begin{split}
\frac{1}{|G|} \sum_{i=1}^r \dim V_i \operatorname{Tr}\left( \rho_i(h^{-1}) \rho_i(g) \right)
& = \left\{
\begin{array}{ll}
\frac{1}{|G|} \sum_{i=1}^r (\dim V_i)^2 & \text{if } g = h \\
\frac{1}{|G|} \sum_{i=1}^r \dim V_i \chi_i(h^{-1} g) & \text{otherwise} \\
\end{array}\right. \\
& = \left\{
\begin{array}{ll}
1 & \text{if } g = h\\
0 & \text{otherwise} \\
\end{array}\right. \\
\end{split}
\] by column orthogonality (Theorem 8.2). Hence \(\mathscr{F}^{-1}(\mathscr{F}(\mathbb{1}_{\{g\}})) = \mathbb{1}_{\{g\}}\) and we conclude the desired result.
Class Functions
Next we consider Fourier theory restricted to the subspace \(\mathscr{C}({G}) \leq \mathscr{L}^{2}({G})\). As we have seen in our build-up to the fundamental theorem of character theory (Lemma 8.1), class functions are exactly the functions whose Fourier transforms are always intertwiners; moreover, as we have seen in homework (Exercise G.5), in the isomorphism \(\mathscr{L}^{2}({G}) \cong \mathbb{C}[G]\), the subspace \(\mathscr{C}({G})\) corresponds to the center of \(\mathbb{C}[G]\).
By Schur’s Lemma (Lemma 5.1), if \(\rho: G \to \operatorname{GL}(V)\) is an irreducible representation and \(f \in \mathscr{C}({G})\), we know that \(\hat{f}(\rho) = \lambda \mathbb{I}\) for some \(\lambda \in \mathbb{C}\). Indeed, in our proof of Theorem 8.1, we saw that \[
\lambda = \frac{|G|}{\dim V} \langle \chi_{V^*}, f \rangle.
\tag{9.3}\] From this perspective, we can greatly simplify Fourier theory for class functions—instead of \(\mathscr{F}(f)\) producing a tuple of linear operators, we can think of it as producing a sequence of scalars (representing the underlying homotheties).
Corollary 9.1 (Fourier theory of class functions) Let \(G\) be a finite group whose irreducible characters are given by \(\chi_{V_1},\dots,\chi_{V_r}\). The Fourier transform gives rise to an isomorphism \[
\begin{aligned}
\mathscr{C}({G}) & \to \mathbb{C}^r \\
f & \mapsto |G| \left( \tfrac{\langle \chi_{V_1^*}, f \rangle}{\dim V_1}, \dots, \tfrac{\langle \chi_{V_r^*}, f \rangle}{\dim V_r} \right),
\end{aligned}
\] whose inverse is given by \[
\begin{aligned}
\mathbb{C}^r & \to \mathscr{C}({G}) \\
(\lambda_1, \cdots, \lambda_r) & \mapsto \frac{1}{|G|} \sum_{i=1}^r \lambda_i\ {\dim V_i}\ \chi_{V_i^*}.
\end{aligned}
\]
Proof. These are the previous formulas, using Equation 9.3 to simplify the Fourier transformation and computing Fourier inversion for the tuple \((\lambda_1 \mathbb{I}, \cdots, \lambda_r \mathbb{I})\). We also note that these equations have a convenient matrix formulation. In particular, if we write \(M\) for the character table as a matrix, \(C = \operatorname{Diag}(\tfrac{|\operatorname{cl}_{}({g_1})|}{|G|}, \dots, \tfrac{|\operatorname{cl}_{}({g_r})|}{|G|})\) (as in Equation 8.1), and \(D = \operatorname{Diag}(\dim V_1, \dots, \dim V_r)\), then encode a class function \(f\) as a column vector by recording the values it takes on each conjugacy class, the above formulas are: \[
f \mapsto |G| D^{-1} M C f \quad \text{ and } \quad \lambda \mapsto \frac{1}{|G|} M^* D \lambda,
\] where the inverse formula uses column orthogonality (Equation 8.2).
9.2 Random Walks
Informally, a random walk in some space describes a repeated process of “steps” taken according to some repeated random decision. A common example is a random walk on the integers as dictated by iterated coin flips, taking steps in the positive direction when the coin comes up heads and in the negative direction if they come up tails. While the theory of walks graphs, infinite lattices, and a variety of other mathematical objects is a rich pursuit, we will restrict our attention to random walks on finite groups. The discussion here is built up from material developed by Diaconis (1988), motivated by random walks on \(\mathcal{S}_{n}\) to model shuffling decks of \(n\) cards.
Probability Distributions
Definition 9.2 Given a finite group \(G\), a probability distribution\(P\) on \(G\) is a function \(P: G \to [0,1]\) satisfying the unitarity axiom: \[
\sum_{h \in G} P(h) = 1.
\] This can be interpreted as choosing a random group element \(g \in G\) from a bag with the associated probability \(P(g)\). Given a subset \(A \subseteq G\), we define \[
P(A) := \sum_{h \in A} P(h),
\] which can be interpreted as the probability of choosing a group element from \(A\) in a random draw. Hence the unitarity axiom can be rephrased as \(P(G) = 1\).
Example 9.3 The uniform distribution on \(G\) is given by \(U(h) = \tfrac{1}{|G|}\) for all \(h \in G\).
Example 9.4 Fix \(g \in G\). The Dirac distribution at \(g\) is given by \(\mathbb{1}_{\{g\}}\).
A probability distribution \(P\) gives rise to a random walk on \(G\) as follows. We begin at time \(k=0\) by standing at \(e \in G\), then draw an element \(g_1 \in G\) according to \(P\) and step to that new place in the group at time \(k=1\). We repeat this process, drawing \(g_2 \in G\) according to \(P\), and step according to multiplication by \(g_2\); that is, we are now standing at \(g_2g_1 \in G\). Continue in this way, using \(P\) to choose how we make our next step. At each step, we have a new probability distribution on \(G\) describing the possible positions we can occupy after \(k\) steps—one can also ask what happens, say, as this number of steps grows to infinity.
Definition 9.3 Let \(f_1, f_2 \in \mathscr{L}^{2}({G})\). The convolution\(f_2 \ast f_1: G \to \mathbb{C}\) is given by \[
(f_2 \ast f_1)(g) = \sum_{h \in G} f_2(gh^{-1}) f_1(h).
\tag{9.4}\] If we think of \(Q\) as describing the initial probabilities of being at any particular place in \(G\), we can interpret \((P \ast Q)(g)\) as describing the probability of standing at \(g \in G\) after taking a random step according to \(P\); we are literally summing over all paths from any starting place \(h \in G\) to \(g\) via multiplication by \(gh^{-1}\).
Note that the convolution is exactly the multiplication needed to make the correspondence \(\mathscr{L}^{2}({G}) \cong \mathbb{C}[G]\) into an isomorphism of \(\mathbb{C}\)-algebras (recall Exercise G.5). Indeed, consider the product of arbitrary elements in \(\mathbb{C}[G]\): \[
\begin{aligned}
\left( \sum_{g \in G} \alpha_g e_g \right) \left( \sum_{h \in G} \beta_h e_h \right) & = \sum_{g,h \in G} \alpha_g \beta_h e_{gh} \\
& = \sum_{g \in G} \left(\sum_{h \in G} \alpha_{gh^{-1}} \beta_h\right) e_g,
\end{aligned}
\tag{9.5}\] where the last equality substitutes \(g \mapsto gh^{-1}\). Of particular interest is the following result:
Proposition 9.2 The convolution of probability distributions is a probability distribution.
Proof. Firstly, \((P \ast Q)(g)\) is nonnegative for all \(g \in G\), because it is the sum of products of nonnegative values. We can compute directly: \[
\begin{split}
\sum_{g \in G} (P \ast Q)(g) & = \sum_{g \in G} \sum_{h \in G} P(g h^{-1}) Q(h) \\
& = \sum_{h \in G} Q(h) \sum_{g \in G} P(g h^{-1}) \\
& = \sum_{h \in G} Q(h) \sum_{g' \in G} P(g') \\
& = \sum_{h \in G} Q(h) = 1,
\end{split}
\] where \(g' = gh^{-1}\). Since \(P \ast Q \geq 0\), we see \(P \ast Q: G \to [0,1]\) is a probability distribution.
Hence, given a rule \(P\) for making random steps, we are are interested in the sequence of probability distributions \(P, P \ast P, P \ast P \ast P, \cdots\). To save ink, we will write \(P^{\ast k}\) for the \(k\)-fold convolution of \(P\) with itself.
Example 9.5 Consider the cyclic groups of order 5 and 6 together with the respective probability distributions \(P: \mathbb{Z}/{5}\mathbb{Z} \to [0,1]\) and \(Q: \mathbb{Z}/{6}\mathbb{Z} \to [0,1]\) defined by \[
P(1) = Q(1) = P(4) = Q(5) = \tfrac{1}{2}
\] and zero otherwise. In other words, these random walks are the repeated process of taking a step to either the right or the left with equal probability. One can compute:
Despite random steps that seem quite similar, the asymptotic behavior of these walks are quite different! We might guess from these initial calculations that the walk on \(\mathbb{Z}/{5}\mathbb{Z}\) is getting ``more and more random,’’ i.e., that \(P^{\ast k} \to U\) as \(k \to \infty\). It also seems like the walk on \(\mathbb{Z}/{6}\mathbb{Z}\) is evening out in some sense, though there is a dependence on the parity of \(k\) preventing the probabilities from becoming uniform. So \(Q^{\ast k}\) does not seem to be converging to \(U\), but we’d still like to say something about the asymptotic behavior. To what distribution does a random walk converge to, if any, and how quickly?—we need better tools!
Note that the convolution is, in general, non-commutative. However:
Proposition 9.3 Let \(P: G \to [0,1]\) be a probability distribution and write \(\mathbb{1}\coloneqq \mathbb{1}_{\{e\}}\). Then we have \[
P \ast \mathbb{1}= P = \mathbb{1}\ast P \quad \text{ and } \quad P \ast U = U = U \ast P.
\] Moreover, the former equation holds if we replace \(P\) with any \(f: G \to \mathbb{C}\). In particular, \(\mathscr{L}^{2}({G})\) equipped with \(\ast\) is a \(\mathbb{C}\)-algebra with identity \(\mathbb{1}\).
Proof. First, we check that \[
(P \ast \mathbb{1})(g) = \sum_{h \in G} P(gh^{-1}) \mathbb{1}(h) = P(g),
\] since \(\mathbb{1}(h) = 0\) unless \(h = e\). Further, if \(P\) is a probability distribution, then we have \[
\begin{aligned}
(P \ast U)(g) & = \sum_{h \in G} P(gh^{-1}) U(h) \qquad & \\
& = \frac{1}{|G|} \sum_{h \in G} P(gh^{-1}) \\
& = \frac{1}{|G|} \sum_{h' \in G} P(h') & (\text{substitute}\ h' = g h^{-1}) \\
& = \frac{1}{|G|} & (\text{unitarity}) \\
\end{aligned}
\] The reverse identities \(\mathbb{1}\ast P = P\) and \(U \ast P = U\) are similar.
The following lemma shows that the non-commutativity is for good reason—convolution is the same as matrix multiplication.
Lemma 9.1 For any \(f_1, f_2: G \to \mathbb{C}\), we have \(\widehat{f_1 \ast f_2}(\rho) = \hat{f_1}(\rho) \hat{f_2}(\rho)\).
Theorem 9.2 The Fourier transform \(\mathscr{F}\) is an isomorphism of \(\mathbb{C}\)-algebras \[
L^2(G) \cong \operatorname{End}(V_1) \oplus \cdots \oplus \operatorname{End}(V_r),
\] where multiplication on the left is convolution and multiplication on the right is the entry-wise composition of linear operators.
Plancherel Formula
In a traditional approach to Fourier theory, say in a differential equations course, the Plancherel theorem states that the integral of a function’s squared modulus is equal to the integral of the squared modulus of its Fourier transform—perhaps after some normalizing by a fixed scalar. In other words, Plancherel states that the Fourier transform is a sort of isometry. While the same result is difficult to ask for in our case, keep this classical motivation in mind when considering the next result.
Theorem 9.3 (Plancherel Formula) Let \(f_1, f_2 \in \mathscr{L}^{2}({G})\). Then \[
\sum_{g \in G} f_1(g^{-1}) f_2(g) = \frac{1}{|G|} \sum_{i=1}^r \dim V_i \operatorname{Tr}\left( \hat{f_1}(\rho_i) \hat{f_2}(\rho_i) \right).
\] In particular, if \(f: G \to \mathbb{R}\) and the \(\rho_i\) are unitary representations, then \[
\|f\|^2 = \frac{1}{|G|^2} \sum_{i=1}^r \dim V_i \operatorname{Tr}\left( \hat{f}(\rho_i)^* \hat{f}(\rho_i) \right).
\]
Proof. For the first formula, for any fixed \(f_2\), both sides of the equation are linear in \(f_1\) and so it is enough to prove for a basis element \(f_1 = \mathbb{1}_{\{g\}}\). The left hand side reads \(f_2(g^{-1})\), and the right is \[
\frac{1}{|G|} \sum_{i=1}^r \dim V_i \operatorname{Tr}\left( \rho_i(g) \widehat{f_2}(\rho_i) \right) = f_2(g^{-1})
\] by the Fourier inversion formula. For the second formula, suppose \(f: G \to \mathbb{R}\) and that \(\rho\) is unitary. If we write \(f'(g) \coloneqq f(g^{-1})\), then \[
\widehat{f'}(\rho) = \sum_{h \in G} f(h^{-1}) \rho(h) = \sum_{g \in G} f(g) \rho(g)^* = \hat{f}(\rho)^*,
\] where we substituted \(g = h^{-1}\) for the penultimate equality.
We also mention how this result specializes to class functions:
Corollary 9.2 If \(f: G \to \mathbb{R}\) is a class function and \(\lambda = (\lambda_1,\dots,\lambda_r)\) represents its Fourier transform as in Equation 9.3, then \[
\|f\|^2 = \frac{1}{|G|^2} \sum_{i=1}^r (\dim V_i)^2 |\lambda_i|^2.
\] As a matrix equation, with \(M\) standing for the character table, \(C = \operatorname{Diag}\left(\tfrac{|\operatorname{cl}_{}({g_1})|}{|G|}, \dots, \tfrac{|\operatorname{cl}_{}({g_r})|}{|G|}\right)\), \(D = \operatorname{Diag}(\dim V_1, \dots, \dim V_r)\), and both \(f\) and \(\lambda\) encoded as column vectors, we have \[
f^* C f = \frac{1}{|G|^2} \lambda^* D^2 \lambda.
\]
As demonstrated by Diaconis (1988), we can use the Plancherel formula as a means to estimate the convergence of the \(k\)-fold convolution of a fixed probability distribution \(P\) to the uniform distribution \(U\). This, together with the Fourier transform and its propensity for rewriting convolutions as products, has many useful applications.
In measuring the difference between two probability distributions \(P, Q: G \to [0,1]\), Diaconis uses the variational distance which detects the largest variation between \(P\) and \(Q\), sampled over all non-empty subsets of \(G\). In symbols: \[
\nu(P,Q) = \max_{A \subseteq G} |P(A) - Q(A)|
\] Given a fixed probability distribution \(P\) on \(G\), we are curious whether \(\nu(P^{\ast k}, U) \to 0\) as \(k\) tends to infinity. While this definition is computationally difficult, there is ia nice reformulation which makes estimating variational distance more tractable.
Lemma 9.2 ((Lemma 3.1, Diaconis 1988)) Let \(Q\) be a probability distribution and write \(\rho_1, \dots, \rho_r\) for the irreducible representations of \(G\), with \(\rho_1\) the trivial representation. Suppose, without loss of generality (Lemma 4.1) that each \(\rho_i\) is unitary. Then \[
\nu(Q,U)^2 \leq \frac{1}{4} \sum_{i=2}^r \dim V_i \operatorname{Tr}\left( \hat{Q}(\rho_i)^* \hat{Q}(\rho_i) \right)
\]
Proof. For the sake of avoiding details that we would not return to otherwise, we leave the start of the proof to Diaconis: a crafty application of the Cauchy–Schwarz inequality gives \[
\nu(Q,U)^2 \leq \frac{|G|}{4} \sum_{h \in G} |Q(h) - U(h)|^2.
\] We compute the Fourier transform of \(f = Q-U\): \[
\begin{gathered}
\hat{f}(\rho_1) = \sum_{h \in G} Q(h) - \sum_{h \in G} U(h) = 1-1 = 0, \quad \text{ and } \\
\hat{f}(\rho_i) = \hat{Q}(\rho_i) - \frac{1}{|G|} \sum_{h \in G} \rho_i(h) = \hat{Q}(\rho_i) \quad \text{for } 1<i\leq r,
\end{gathered}
\] where the last equality follows because \(\hat{U}(\rho_i)\) projects (Theorem 5.2) onto the invariant subspace of \(V_i\) (which is the zero subspace if \(V_i\) is a non-trivial irreducible representation). By the second version of the Plancherel formula, we have \[
\begin{aligned}
\nu(Q,U)^2 & \leq \frac{1}{4} \sum_{i=1}^r \dim V_i \operatorname{Tr}(\hat{f}(\rho_i)^* \hat{f}(\rho_i)) \\
& = \frac{1}{4} \sum_{i=2}^r \dim V_i \operatorname{Tr}(\hat{Q}(\rho_i)^* \hat{Q}(\rho_i)).
\end{aligned}
\]
In particular, substituting \(P^{\ast k}\) for \(Q\) in the upper bound lemma gives \[
\nu(P^{\ast k},U)^2 \leq \frac{1}{4} \sum_{i=2}^r \dim V_i \operatorname{Tr}\left( \left(\hat{P}(\rho_i)^k\right)^* \hat{P}(\rho_i)^k \right).
\tag{9.6}\]
Example 9.6 ((Theorem 3.2, Diaconis 1988)) Let us revisit the case of random walks on cyclic groups, where we only consider groups of odd order to avoid the alternating phenomena we observed. Consider \(G = \mathbb{Z}/{(2n+1)}\mathbb{Z}\), the probability distribution \(P(1) = P(2n) = \frac{1}{2}\) and zero otherwise, and write \(\zeta = e^{\tfrac{2\pi}{2n+1} i}\). Then \[
\hat{P}(\rho_j) = \sum_{k=0}^{2n} P(k) \zeta^{jk} = \frac{1}{2} \left( \zeta^j + \zeta^{-j} \right) = \cos(\tfrac{2\pi j}{2n+1}).
\]
Next, beware an off-by-one-error in translating from the Upper Bound Lemma as stated, since we index the irreducibles of \(G\) from \(0\) to \(2n\) instead of \(1\) to \(2n+1\). Using the inequality \(\cos t \leq e^{-t^2/2}\) for all \(t \in [0,\tfrac{\pi}{2}]\), we apply the Lemma: \[
\nu(P^{\ast k},U) \leq \frac{1}{4} \sum_{j=1}^{2n} \cos^{2k}(\tfrac{2\pi j}{2n+1}) = \frac{1}{2} \sum_{j=1}^{n} \cos^{2k}(\tfrac{\pi j}{2n+1}) \leq \frac{1}{2} \sum_{j=1}^n e^{-\tfrac{\pi^2 j^2 k}{(2n+1)^2}},
\] where the middle equality matches terms across the unit circle. With a bit more work, Diaconis shows, for \(n \geq 3\) and \(k \geq (2n+1)^2\), that \[
\nu(P^{\ast k},U) \leq e^{-\tfrac{\pi^2 k}{2(2n+1)^2}}.
\] In other words, we can now rigorously conclude \(P^{\ast k} \to U\) as \(k \to \infty\) at an exponential rate.
An interested mathematician can now begin to approach the problem of shuffling a deck of \(n\) cards, under the guise of a random walk on the permutation group \(\mathcal{S}_{n}\). We do not currently have enough knowledge of the representation theory of \(\mathcal{S}_{n}\) to actually solve this problem, nor have we developed the statistics available to tackle the “riffle” shuffle popular in card games—see Bayer and Diaconis (1992). Instead, we shall construct a very simple model, and indicate how it and the tools of representation theory would be used to attack much more complicated scenarios.
Example 9.7 ((Section 3D, Diaconis 1988)) Consider the shuffling procedure for a deck of \(n\) cards consisting of selecting two (not necessarily distinct) cards at random and transposing them. Thus we have the probability distribution \[
P(\sigma)= \left\{ \begin{array}{ll}
\tfrac{1}{n} & \text{if } \sigma = e \\
\tfrac{2}{n^2} & \text{if } \sigma \text{ is a 2-cycle} \\
0 & \text{otherwise.}
\end{array} \right.
\] Diaconis uses the upper bound Lemma to control the rate at which \(\nu(P^{\ast k},U)\) tends to zero. While we cannot replicate his argument with our current tools, we can at least begin and see where the analysis leads us.
First we compute: \[
\hat{P}(\rho) = \sum_{\sigma \in \mathcal{S}_{n}} P(\sigma) \rho(\sigma) = \frac{1}{n} \mathbb{I}+ \frac{2}{n^2} \sum_{\mathclap{\text{2-cycles}}} \rho(\sigma)
\] On the other hand, since \(P\) is a class function, \(\hat{P}(\rho)\) is an intertwiner by Lemma 8.1. As in our proof of Corollary 9.1 , if \(\rho\) is irreducible, Schur’s Lemma says that \(\hat{P}(\rho) = \lambda \mathbb{I}\). We take the trace: \[
\frac{1}{n} \dim V + \frac{2}{n^2} \binom{n}{2} \chi((1\;2)) = \lambda \dim V,
\] which means that \(\lambda = \frac{1}{n} + \frac{n-1}{n} \frac{\chi((1\;2))}{\dim V}\). By the upper bound Lemma, we have \[
\begin{split}
\nu(P^{\ast k},U) & \leq \frac{1}{4} \sum_{i=2}^r \dim V_i \operatorname{Tr}\left[ (\hat{P}(\rho_i)^k)^* \hat{P}(\rho_i)^k \right] \\
& = \frac{1}{4} \sum_{i=1}^r \dim V_i \left( \frac{\dim V_i}{n} + \frac{n-1}{n} \chi_i((1\;2)) \right)
\end{split}.
\] While we cannot proceed further, we can see that knowing the first two columns of the associated character table would allow us to proceed in controlling this inequality.
Of course, randomly transposing cards is not a realistic simulation of shuffling in most contexts. The dovetail “riffle” shuffle is the most commonly used method of randomization in professional gambling contexts, which can be modeled as follows: A deck of \(n\) cards is cut into two portions according to a binomial distribution, which are then reintegrated so that cards drop from the left or right heaps with probability proportional to the number of cards in each heap. This assumption culminates in the Gilbert–Shannon–Reeds model \(P\). This analysis was leveraged in Bayer–Diaconis’ paper (1992) along with the representation theory of \(\mathcal{S}_{n}\) to show that, in a deck of 52 cards, the variational distance \(\nu(P^{\ast k},U)\) remains nearly at its maximum of 1 for up to five shuffles before decreasing sharply by roughly factors of two each shuffle.
This sudden convergence is known as a cutoff phenomenon. The following table illustrates the total variational distance for \(k\) shuffles for various collections of \(n\) cards:
\[
\begin{array}{rr|cccccccccc}
& & & & & & k \\
& & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline
& 25 & 1.000 & 1.000 & 0.999 & 0.775 & 0.437 & 0.231 & \cellcolor[gray]{0.6} 0.114 & 0.056 & 0.028 & 0.014 \\
& 35 & 1.000 & 1.000 & 1.000 & 0.929 & 0.597 & 0.322 & 0.164 & \cellcolor[gray]{0.6} 0.084 & 0.042 & 0.021 \\
& 52 & 1.000 & 1.000 & 1.000 & 1.000 & 0.924 & 0.614 & 0.334 & 0.167 & \cellcolor[gray]{0.6}0.085 & 0.043 \\
n & 78 & 1.000 & 1.000 & 1.000 & 1.000 & 1.000 & 0.893 & 0.571 & 0.307 & 0.153 & \cellcolor[gray]{0.6}0.078 \\
& 104 & 1.000 & 1.000 & 1.000 & 1.000 & 1.000 & 0.988 & 0.772 & 0.454 & 0.237 & \cellcolor[gray]{0.6}0.119 \\
& 208 & 1.000 & 1.000 & 1.000 & 1.000 & 1.000 & 1.000 & 1.000 & 0.914 & 0.603 & 0.329 \\
& 312 & 1.000 & 1.000 & 1.000 & 1.000 & 1.000 & 1.000 & 1.000 & 0.999 & 0.883 & 0.565 \\
\end{array}
\] Bayer and Diaconis showed that roughly \(\frac{3}{2} \log_2 n\) shuffles are necessary and sufficient to randomize \(n\) cards, i.e., to surpass this cutoff threshhold. Note that the entry corresponding to the nearest integer \(k\) to \(\frac{3}{2} \log_2 n\) is shaded on the previous table. These results are the most well known regarding the amount of shuffles required to sufficiently randomize a deck. This is often cited more succinctly as:
“A deck does not start to become random until five good shuffles, and is reliably randomized after seven.”
Lots of magic (and casino protocol) relies on this phenomena!
Class Functions
As we saw, the Fourier transform and Plancherel formula simplify considerably when we restrict our attention to class functions (Corollary 9.1, Corollary 9.2).
In an abuse of notation, we continue to write the Fourier transform of \(f \in \mathscr{C}({G})\) as \(\mathscr{F}(f)\) but conflate the scalar maps \[
(\lambda_1 \mathbb{I}, \dots, \lambda_r \mathbb{I}) \in \operatorname{End}(V_1) \oplus \cdots \oplus \operatorname{End}(V_r)
\] with the tuple \((\lambda_1,\dots,\lambda_r) \in \mathbb{C}^r\)
We pause to survey the scene, especially in light of the isomorphisms (Exercise G.5) between \(\mathscr{L}^{2}({G})\), \(\mathbb{C}[G]\), and the sum of endomorphism algebras for each irreducible via the Fourier transform. We have the following diagram, where every horizontal map is an isomorphism of \(\mathbb{C}\)-algebras and every vertical map is an inclusion.
The bottom arrows being isomorphisms follow from the fact that isomorphisms of \(\mathbb{C}\)-algebras restrict to isomorphisms of centers.
Example 9.8 Consider the random walk on \(\mathcal{S}_{n}\) via transpositions (Example 9.7) in the case \(n=5\). In this case, we see that the Fourier transform is given by \[
\mathscr{F}(P) = \left( 1, -\tfrac{3}{5}, \tfrac{3}{5}, -\tfrac{1}{5}, \tfrac{9}{25}, \tfrac{1}{25}, \tfrac{1}{5} \right),
\] as we can see from Listing 9.2 (with a nod to Exercise F.3).
Listing 9.2: Transposition walk on a symmetric group
Because of this simple form—the product of scalar matrices is simply given by the product of their scalars—it is easy to compute the Fourier transform of the iterated convolution \(P^{\ast k}\): \[
\mathscr{F}(P^{\ast k}) = \mathscr{F}(P)^k = \left( 1, \left(-\tfrac{3}{5}\right)^k, \left(\tfrac{3}{5}\right)^k, \left(-\tfrac{1}{5}\right)^k, \left(\tfrac{9}{25}\right)^k, \left(\tfrac{1}{25}\right)^k, \left(\tfrac{1}{5}\right)^k \right).
\] Hence, as \(k \to \infty\), we can see that \(\mathscr{F}(P^{\ast k}) \to (1,0,0,0,0,0,0)\). Recall that this is exactly the Fourier transform of the uniform distribution \(U\)! Thus we see that \(P^{\ast k} \to U\) at a rate comparable to the speed at which \((\tfrac{3}{5})^k\) shrinks to zero.
Note how easy the question of convergence becomes after applying the Fourier transform of a class function—we need only know what happens to the scalars \(\lambda^k\) as \(k\) grows to infinity. Moreover, as in the proof of Proposition 7.1, for any representation \(\rho: G \to \operatorname{GL}(V)\) we have observed that \(|\chi(h)| < \dim V\) for all \(h \in G\). Hence, by the triangle inequality, we have \[
|\hat{P}(\rho)| = \left| \frac{1}{\dim V} \sum_{h \in G} P(h) \chi(h) \right| \leq \sum_{h \in G} \left| \frac{\chi(h)}{\dim V} \right| P(h) \leq \sum_{h \in G} P(h) = 1,
\] where the second inequality follows because \(P(h) \geq 0\) for each \(h \in G\). All told:
Proposition 9.4 Let \(P: G \to [0,1]\) be a probability distribution that is also a class function. Then each scalar \(\lambda_i \in \mathbb{C}\) in the Fourier transform \(\mathscr{F}(P)\) has \(|\lambda_i| \leq 1\)
Note further that \(\lambda_1\), the scalar corresponding to the trivial representation, is always equal to \(1\) due to the unitarity condition. Thus we have three different scenarios:
The \(\lambda_i\) for \(i > 2\) are all strictly smaller than \(1\) in norm, and \(P^{\ast k}\) converges to \(U\). The convergence happens at a rate asymptotically equal to \[
\left( \max_{i\geq 2} |\lambda_i| \right)^k \to 0.
\]
At least one of the scalars \(\lambda_i\) for \(i>2\) is equal to a non-trivial root of unity, so that \(P^{\ast k}\) oscillates between multiple steady states but does not converge.
We have some \(\lambda_i = 1\) for \(i>2\), but all others have \(|\lambda_i|<1\). Then \(P^{\ast k}\) converges to the inverse Fourier transform of the vector where each \(\lambda_i\) with norm smaller than \(1\) has been replaced with \(0.\)
Example 9.9 Consider the random walk on \(\mathcal{A}_{4}\) as dictated by the distribution \[
P(\sigma) = \left\{ \begin{array}{ll}
\frac{1}{4} & \text{if } \sigma \text{ is conjugate to } (1\;2\;3) \\
0 & \text{otherwise.}
\end{array} \right.
\] Using the table as described in Example 8.1, we represent \(P\) by the vector \((0, \tfrac{1}{4}, 0, 0)\) and find that \(\mathscr{F}(P) = (1,\zeta,\zeta^2,0)\). We can see entry-wise powers of \(\mathscr{F}(P)\) alternate between \[
(1,\zeta,\zeta^2,0), \quad (1,\zeta^2,\zeta,0), \quad \text{ and } \quad (1,1,1,0),
\] whose inverse Fourier transforms are \((0,\tfrac{1}{4},0,0)\), \((0,0,\tfrac{1}{4},0)\), and \((\tfrac{1}{4},0,0,\tfrac{1}{4})\), respectively, which are the uniform distributions on \(\operatorname{cl}_{}({(1\ 2\ 3)})\), \(\operatorname{cl}_{}({(1\ 2\ 3)})\), and \(\langle(1\ 2)(3\ 4)\rangle\). So while \(P^{\ast k}\) does not converge, we still understand the asymptotic behavior of the random walk.
Example 9.10 Consider the random walk on \(\mathcal{S}_{4}\) given by \[
P(\sigma) = \left\{
\begin{array}{ll}
\tfrac{1}{4} & \sigma = \mathbb{I}\\
\tfrac{1}{16} & \sigma \text{ is a $3$-cycle} \\
\tfrac{1}{12} & \sigma \text{ is a $(2,2)$-cycle} \\
0 & \text{otherwise}.
\end{array}
\right.
\] We apply the following SageMath code:
Listing 9.3: Random walk transforms on a symmetric group
From here, we see that \(\mathscr{F}(P) = (1, 1, \tfrac{1}{6}, \tfrac{1}{6}, \tfrac{1}{4})\), and hence \(\mathscr{F}(P^{\ast k}) \to (1, 1, 0, 0, 0)\) as \(k \to \infty\) at a rate dominated by \(\frac{1}{4^k}\). In particular, we compute \(\mathscr{F}^{-1}(1, 1, 0, 0, 0) = (\frac{1}{12}, 0, \frac{1}{12}, \frac{1}{12}, 0)\) via:
In other words, we see that \(P^{\ast k}\) converges to the uniform distribution supported on \(\mathcal{A}_{4} \unlhd\mathcal{S}_{4}\)!
Example 9.11 Consider the random walks on \(\operatorname{Aff}_{1}({\mathbb{F}_5})\) (Example 8.7) given by \[
P(M) = \left\{ \begin{array}{ll}
\tfrac{1}{6} & M = \mathbb{I}\\
\tfrac{1}{6} & \det(M) = 3 \\
0 & \text{otherwise}
\end{array} \right. \quad \text{ and } \quad Q(M) = \left\{ \begin{array}{ll}
\tfrac{1}{5} & \det(M) = 3 \\
0 & \text{otherwise.}
\end{array} \right.
\] With the power of SageMath (Listing 9.4) and the previously calculated character table, we compute:
Listing 9.4: Random walk transforms on an affine group
So the Fourier transform of these distributions is given by \[
\mathscr{F}(P) = (1, -\tfrac23, 1, -\tfrac23, \tfrac16) \quad \text{ and } \quad \mathscr{F}(Q) = (1, -1, 1, -1, 0).
\] It is much easier to compute the asymptotic behavior of these tuples, exponentiated entry-wise, than to calculate iterated convolutions of \(P\) and \(Q\). We see that \[
\lim_{k \to \infty} \mathscr{F}(P)^k = \lim_{k \to \infty} (1, (-\tfrac23)^k, 1, (-\tfrac23)^k, (\tfrac16)^k) = (1, 0, 1, 0, 0),
\] whereas \(\mathscr{F}(Q)^k\) oscillates between \((1,-1,1,-1,0)\) and \((1,1,1,1,0)\) depending on the parity of \(k\). The inverse transform of these limiting tuples gives: \[
\begin{gathered}
\mathscr{F}^{-1}(1, 0, 1, 0, 0) = (\tfrac{1}{10}, \tfrac{1}{10}, 0, \tfrac{1}{10}, 0), \\
\mathscr{F}^{-1}(1, 1, 1, 1, 0) = (\tfrac15,\tfrac15,0,0,0).
\end{gathered}
\] Which we can compute via
We conclude that \(P^{\ast k}\) converges to the uniform distribution on the subgroup \(\langle \begin{psmallmatrix}
1 & 1 \\ 0 & 1
\end{psmallmatrix}, \begin{psmallmatrix}
3 & 0 \\ 0 & 1
\end{psmallmatrix} \rangle\) at a rate dominated by \((\tfrac{2}{3})^k\), while \(Q^{\ast k}\) oscillates between the uniform distribution on the conjugacy class of \(\begin{psmallmatrix}
3 & 0 \\ 0 & 1
\end{psmallmatrix}\) to the uniform distribution on the subgroup \(\langle \begin{psmallmatrix}
1 & 1 \\ 0 & 1
\end{psmallmatrix} \rangle\).
For its relevance to the discussion at hand, we mention one additional result before concluding our survey of random walks on finite groups. For the next result, keep in mind Exercise C.3 and Exercise G.2:
Proposition 9.5 Let \(G\) be a finite group with \(N \unlhd G\) and consider the uniform distribution on \(N\): \[
U_N = \frac{1}{|N|} \mathbb{1}_{N}.
\] Then the \(i\)-th Fourier coefficient \(\lambda_i\) of \(U_N\) is \(1\) if and only if \(\rho_i\) has \(N\) in its kernel, i.e., \(\rho_i\) is a lift of some representation of \(G/N\). More generally, \(\lambda_i = \frac{\dim V_i^N}{\dim V_i}\), where \(V_i^N\) is the \(N\)-invariant subspace (Exercise C.3).
Proof. First recall that a subgroup is normal if and only if it can be written as a union of conjugacy classes (Remark 3.5). In particular, we enumerate conjugacy class representatives \(g_1,\dots,g_r\).
It behooves us to compute the Fourier transform of the indicator functions \(\mathbb{1}_{\operatorname{cl}_{}({g_i})}\). If we also enumerate the irreducible representations of \(G\) as \(\rho_1,\dots,\rho_r\) and then write \(\mu_{ij}\) as the scalar corresponding to the operator \(\widehat{\mathbb{1}_{\operatorname{cl}_{}({g_i})}}(\rho_i)\), we can directly compute \[
\mu_{ij} \dim V_i = \operatorname{Tr}\left(\widehat{\mathbb{1}_{\operatorname{cl}_{}({g_j})}}(\rho_i)\right) = \sum_{\mathclap{h \in \operatorname{cl}_{}({g_j})}} \chi_i(h) = |\operatorname{cl}_{}({g_j})|\ \chi_i(g_j).
\] So the \(i\)-th Fourier coefficient of the indicator function for the \(j\)-th conjugacy class is \(\tfrac{|\operatorname{cl}_{}({g_j})|}{\dim V_i} \chi_i(g_j)\). If we write \(S \subseteq \{1,\dots,r\}\) for the subset of conjugacy classes whose union is \(N\), then \[
U_N = \frac{1}{|N|} \sum_{j \in S} \mathbb{1}_{\operatorname{cl}_{}({g_j})}.
\] By linearity of the Fourier transform, if \(N \leq \ker \rho_i\), then the \(i\)-th Fourier coefficient of \(U_N\) is \[
\lambda_i = \sum_{j \in S} \mu_{ij} = \frac{1}{|N|} \sum_{j \in S} \frac{|\operatorname{cl}_{}({g_j})|}{\dim V_i} \chi_i(g_j) = \frac{1}{|N|} \sum_{j \in S} |\operatorname{cl}_{}({g_j})| = 1.
\] More generally, notice that the left hand side looks suspiciously like the \(\mathscr{L}^{2}({G})\) inner product for class functions on \(N\). With this in mind, we can rewrite all the above as \[
\lambda_i = \frac{1}{|N|} \sum_{j \in S} \frac{|\operatorname{cl}_{}({g_j})|}{\dim V_i} \chi_i(g_j) = \frac{1}{\dim V_i} \langle 1, \chi_i \rangle_{\mathscr{L}^{2}({N})} = \frac{\dim V_i^N}{\dim V_i},
\] which is equal to \(1\) if and only if \(\dim V_i^N = \dim V_i\).
Cayley Graphs
We conclude with SageMath code to visualize some of the walks mentioned above. First, we include several blurbs which can be used to implement the probability distributions (in terms of the arithmetic of the group algebra, since \(\mathbb{C}[G] \cong \mathscr{L}^{2}({G})\)). For consistency, these are all done by realizing each \(G\) as a permutation group. Lastly, we include a single visualization block which shows the walk via Cayley graphs, where hot color indicates high probabilities; cold color is low; and white is near uniform.
G = SymmetricGroup(4)L2 = GroupAlgebra(G, QQ)three_cycles = [g for g in G if g.cycle_type() == [3, 1]]two_two_cycles = [g for g in G if g.cycle_type() == [2, 2]]P = (1/4)*L2(G(())) +\sum((1/16)*L2(g) for g in three_cycles) +\sum((1/12)*L2(g) for g in two_two_cycles)P_limit =sum(2/G.order()*L2(g) if g.sign() ==1else0for g in G)
Visualization
# We expect G, L2, P, and P_limit to be defined, as in the above blurbs# Note that P_limit = None defaults to the uniform distribution on Gimport matplotlib.pyplot as pltcmap = plt.get_cmap('coolwarm')cayley_graph = G.cayley_graph()fixed_pos = cayley_graph.layout(layout='spring')def variation_distance(P, Q, group):if Q isNone: Q =sum((1/G.order()) * L2(g) for g in G)return0.5*sum(abs(float(P[g]) -float(Q[g])) for g in group)def plot_walk(walk_step, algebra_dist, target_dist=None): dist = variation_distance(algebra_dist, target_dist, G) vertex_colors = {}for v in cayley_graph.vertices(sort=True): p =float(algebra_dist[v]) u =1.0/ G.order() if p == u: color_intensity =0.5elif p < u: color_intensity =0.5* (p / u)^0.25else: color_intensity =0.5+0.5* ((p - u) / (1.0- u))^0.25 color = cmap(color_intensity)[:3]if color notin vertex_colors: vertex_colors[color] = [] vertex_colors[color].append(v) title_str =f"Step: {walk_step} | Distance: {dist:.4f}" p = cayley_graph.plot(vertex_colors=vertex_colors, pos=fixed_pos, vertex_labels=False, vertex_size=300, title=title_str)return p, distdef visualize_walk(plot_steps, initial_dist, target_dist=None, show_cayley=True): plots = {} distances = [] algebra_dist = L2(G(())) last_step =0for n insorted(plot_steps): algebra_dist *= initial_dist^(n - last_step) last_step = nif show_cayley: plot, dist = plot_walk(n, algebra_dist, target_dist=target_dist) plots[n] = plot distances.append((n, dist))else: distances.append(variation_distance(algebra_dist, target_dist, G))if show_cayley:for n in plots: filename =f"walk_step_{n}.png" plots[n].save(filename)print(f" Saved {filename}") dist_plot = list_plot(distances, plotjoined=True, marker='o', color='blue', axes_labels=['Step ($n$)', 'Total Variation Distance']) dist_plot.save("variational_distance.png")print(" Saved variational_distance.png")return dist_plot# Visualize visualize_walk([1, 2, 3, 4, 10, 11, 20, 21, 100, 101], P, target_dist=P_limit)
Bayer, Dave, and Persi Diaconis. 1992. “Trailing the Dovetail Shuffle to Its Lair.”The Annals of Applied Probability, 294–313.
Diaconis, P. 1988. Group Representations in Probability and Statistics. IMS Lecture Notes. Institute of Mathematical Statistics.