I have finally finished the first draft of my PhD thesis. My advisor Dr Stephen Wills is presently reading through it and will get back to me with his comments in the next few weeks. The project was successful in that I managed to prove the Diaconis-Shahshahani Upper Bound Lemma for finite quantum groups… how successful my application of the Lemma to concrete examples is probably open to debate. First draft of abstract and introduction — without references — below the fold.


Of central interest in the study of random walks on finite groups are ergodic random walks. Ergodic random walks converge to random in the sense that as the number of transitions grows to infinity, the state-distribution converges to the uniform distribution on G. The study of random walks on finite groups is generalised to the study of random walks on quantum groups. Plainly speaking, quantum groups are neither groups nor sets and rather what are studied are finite dimensional algebras that have the same properties as the algebra of functions on an actual group — except for commutativity.

The concept of a random walk converging to random — and a metric for measuring the distance to random after k transitions — is generalised to the case of random walks on quantum groups.

A central tool in the study of ergodic random walks on finite groups is the Upper Bound Lemma of Diaconis & Shahshahani. The Upper Bound Lemma uses the representation theory of the group to generate upper bounds for the distance to random and thus can be used to determine convergence rates for ergodic walks. The representation theory of quantum groups is very well understood and is remarkably similar to the representation theory of classical groups. This allows for a generalisation of the Upper Bound Lemma to an Upper Bound Lemma for quantum groups.

The Quantum Diaconis-Shahshahani Upper Bound Lemma is used to study the convergence of ergodic random walks on classical groups \mathbb{Z}_n, \mathbb{Z}_2^n, the dual group \widehat{S_n} as well as the `truly’ quantum groups of Kac & Paljutkin and Sekine.

Note that for all of these generalisations, restricting to commutative subalgebras gives the same definitions and results as the classical theory.


The innocuous-sounding question — how many shuffles are required to mix up a deck of cards? — leads to considering `shuffles’ \sigma_i\in S_{52} chosen according to a fixed probability distribution, and asking how large should k be so that the distribution of the random variable

\displaystyle \sigma_k\cdots \sigma_2\cdot\sigma_1

is approximately uniform on S_{52}. The culture of generalisation in mathematics leads us to consider the following problem. Given a finite group, G, and elements g_i\in G chosen according to a fixed probability distribution, how large should k be so that the distribution of the random variable

g_k\cdots g_2\cdot g_1

is approximately uniform on G? Such problems arise in the theory of random walks on finite groups and were the subject of the author’s MSc thesis.

It became apparent during the development of quantum mechanics that classical, Kolmogorovian probability was unable to describe quantum mechanical phenomena such as, for example, Heisenberg’s Uncertainty Principle. Just like the fact that classical probability had been studied for years before Kolmogorov lay down the measure-theoretic, axiomatical foundation of the subject in the early 1930s (ironically not very long after the work of Hilbert, Dirac, Von Neumann and others on quantum mechanics), quantum probability had been studied — primarily in the field of quantum mechanics — for the bones of half a century before maturing in the 1970s and 1980s. Taking a line through the uncertainty principle, observables a and b (measurable quantities) need not commute: the observable ab need not be the same as the observable ba, and therefore, rather than a real-valued function on a state space, observables might behave more like matrices. Considering further postulates about the nature of quantum mechanics (justified by the experimental verification of their consequences), Dirac & von Neumann were led to the following axioms:

  •  the observables of a quantum mechanical system are defined to be the self-adjoint elements of a \mathrm{C}^*-algebra.
  • the states of a quantum mechanical system are defined to be the states of the \mathrm{C}^*-algebra.
  • the value \rho(a) of a state \rho on an element a is the expectation value of the observable a if the quantum system is in the state \rho.

Moving away from quantum mechanics, the basic definition in quantum probability is that of a quantum probability space, sometimes referred to as a noncommutative or algebraic probability space.

A quantum probability space is a pair (A,\rho), where A is a {}^*-algebra and \rho is a state.

This definition is a generalization of the definition of a probability space in Kolmogorovian probability theory, in the sense that every (classical) probability space, \Omega, gives rise to a quantum probability space if A is chosen as \mathcal{L}^\infty(\Omega), the {}^*-algebra of bounded complex-valued measurable functions on it. Indeed every `quantisation’ of classical probability should, ideally, agree with the classical definition if restricted to a commutative subalgebra.

Considered as a research programme, quantum probability is concerned with generalising, where possible, objects in the study of classical probability to quantised objects in the study of quantum probability theory. It is under this programme that this work lies: the study of random walks on finite groups uses classical probability theory — a study of random walks on quantum groups should be the corresponding area of study in quantum probability.

Therefore, this work is concerned with a generalisation of a generalisation of card shuffling: generalising, where possible, the ideas and results presented in the MSc thesis to the case of quantum groups. The problem is that while the central object of card shuffling — the set of shuffles — is generalised to that of a set of elements of a group, the generalisation to quantum groups moves away from a `set of points’ interpretation. For those new to the area (such as the author at the beginning of this study), this can cause serious problems — particularly because this generalisation means a dearth of intuition. Going back to quantum mechanics, the fact that one of the most successful physics theories of our time says frankly unimaginable things about the nature of reality — space is not as we comprehend and perhaps even incomprehensible — leads to famous quotes such as those of Niels Bohr:

If quantum mechanics hasn’t profoundly shocked you, you haven’t understood it yet.

However, in this study of random walks on finite quantum groups at least, the quantum theory generalises so nicely from the classical setup that it can be fruitful to refer to quantum groups and associated virtual objects as if they really exist. This has become more and more common in the quantum group field and is a helpful development in the author’s opinion: this approach is utilised as often as possible in this work. As is commented upon later, at the very least this approach gives a most pleasing notation for quantised objects (in fact some papers simply denote a quantum group by G not paying much credence to the fact that it isn’t actually a `set of points’ group). For examples of this approach see recent papers on quantum groups such as by Banica & Meszaros, Franz, Kula & Skalski and Skalski & Soltan.

Starting in the 1980s with the work of Drinfeld, Jimbo and (later) Woronowicz, there are many motivations for and approaches to quantum groups (although in finite dimensions, the majority of approaches are equivalent). As this study concerns random walks on finite quantum groups, this recent history of the motivations for and approaches to quantum groups is largely irrelevant. Briefly, while quantum groups were first spoken about in the 1980s, the objects studied in this thesis can be traced back to work by Heinz Hopf in the 1940s and Kac in the 1960s. Please see the introduction by Timmermann to learn more about the motivations for and approaches to quantum groups.

Random walks on finite quantum groups were first studied by Franz & Gohm. The random walks of interest in the classical case, largely, are those which converge in distribution to the uniform or random distribution, \pi. The question that is asked about these classical random walks are as per the shuffling question. Asking this question in a more precise way involves putting a metric on the set of probabilities on a group, and asking, where \Psi_k is the distribution of the product of k group elements (sampled by a fixed probability distribution), for a given \varepsilon>0, how large must k be to ensure that d(\Psi_k,\pi)<\varepsilon? As far as the author knows, this question has not been asked for random walks, in the sense of Franz & Gohm, on finite quantum groups. The quantisation of a `random walk on a group converging to random’ is a random walk on a finite quantum group converging in distribution to the Haar state (which will eventually be denoted by \pi also). This work, in Chapter 4, gives the appropriate metric to measure the distance between the quantised distribution, \Psi_k, of the random walk after k transitions, and the random distribution \pi.

Returning to quantum mechanics briefly, a classical random walk on a finite group G can be viewed as a quantum mechanical system evolving by transitioning from state to state at discrete times. Assume furthermore that the random walk sits in a lidded black box. The algebra of complex-valued functions on G, F(G), is a commutative \mathrm{C}^*-algebra and can be concretely realised as the set of diagonal operators on \mathbb{C}^{|G|}. Thus, the observables are |G|\times |G| diagonal matrices with real entries i.e. the real-valued functions on G. Note that the measurement of an observable f is one of the eigenvalues of the associated linear operator. The eigenvalues of a diagonal operator are the elements along the diagonal — in other words the function values \{f(g):g\in G\}. The state after k transitions is given by a state \Psi_k on F(G) i.e. integration against a probability distribution distribution, \mu_k. Therefore the expectation of an observable f after k transitions is given by the

\Psi_k(f)=\int_G f(g)\,d\mu_k(g).

Taking the Copenhagen interpretation of quantum mechanics, after k transitions, the wavefunction/state \Psi_k describes the random walk completely and that is all that can be said. However if an observable f is to be measured, the system must be interfered with: the lid must be lifted off. If the result of the measurement of f yields f(s) then the wavefunction has collapsed into the state s (or rather \delta^s). A model for a random walk is, of course, a cat (bearing a collar with the note “If found please call 01-6680748 and ask for E.S.”) inside a large black room containing a structure modelling the Cayley graph of the group, moving from node to node in a seemingly random manner. Given some observable f — perhaps the height of the node upon which the cat sits — before opening the door, all that can said about the result of measuring f after k transitions is the expectation, \Psi_k(f). However, upon opening the door, the observer could see at this kth transition of the walk that the cat was on the node labelled s and thus everything was known about the result of the measurement: it would certainly yield the eigenvalue f(s).

Now thinking about a random walk on a finite, classical group converging to random, what can be imagined is that no matter what observable f is considered, as more and more transitions are made, then — with the lid on — less and less is known about the state of the random walk in the black box. No good prediction can be made about where the random walk is after k transitions and the random walk is — approximately — uniformly distributed on G. If the random walk is uniformly distributed, the expectation of f is nothing but the mean-average of f.

Therefore, although the algebra of functions on a finite quantum group is defined in this work to be a finite but not-necessarily-commutative \mathrm{C}^*-algebra — therefore without a `set of points’ interpretation to parameterise the states — the self-adjoint elements of the \mathrm{C}^*-algebra can still be considered observables whose eigenvalues are the result of measuring the state of the random walk. If converging to the Haar state is to be considered in the same way as the classical case — that the Haar state h is integration against the uniform measure and so h(a) is interpreted as the average of a — then a random walk on a quantum group converging to random shares the property of random walks on classical groups — that as more and more transitions are made, the expectation of any observable is nothing but the mean-average.

This thesis shows that for given families of random walks on \mathbb{Z}_n, \mathbb{Z}_2^n, \widehat{S_n} and \mathbb{KP}_n, respectively, \mathcal{O}(n^2), \mathcal{O}(n\ln n), \mathcal{O}(n^n) and \mathcal{O}(n^2) transitions are sufficient for convergence to random. The first two random walks have been studied before, however while it isn’t claimed that convergence rates for random walks on dual groups (the convergence in \mathcal{O}(n^n) transitions for the random walk on \widehat{S_n}) haven’t been studied before, as far as the author knows, for a truly quantum group, or rather family of quantum groups, such as \mathbb{KP}_n, this is the first time that explicit convergence rates have been studied.

One of the most exciting and potentially lucrative aspects of quantum probability, or rather more specifically quantum group theory, is that theorems about finite groups may in fact be true for quantum groups also. For example — and a lot of this thesis hangs upon this — the finite Peter-Weyl Theorem concerning the matrix elements of representations of classical groups is exactly the same as the finite Peter-Weyl Theorem  for quantum finite groups in the sense that replacing in the classical statement `finite group, G‘ with ‘finite quantum group, \mathbb{G}‘ yields the quantum statement. What this really means is that the classical finite Peter-Weyl Theorem is actually just a special case of the quantum finite Peter-Weyl Theorem (itself a special case of the Peter-Weyl Theorem (for compact quantum groups)).

This is rather comforting on the conceptional level — these quantum objects behave so much like their ‘set of points’ classical counterparts — but it is on the pragmatic level of proving results about these quantum objects that this principle really comes to the fore. On the one hand, some theorems concerning the theory of finite groups are just corollaries to results about quantum groups. On this other, pragmatic, hand, there is a transfer principle: any proof of a classical group theorem, written without regard to any of the points in the ‘set of points’, may be directly translatable into a proof of the corresponding quantum group theorem.

In this work, the hero of this transfer principle is the Haar state, h, which frequently allows `sum over points’ arguments & statements about elements of an f:G\rightarrow \mathbb{C} in the algebra of functions on a finite group, G, to be transferred via:

\underbrace{\frac{1}{|G|}\sum_{t\in G}f(t)}_{\text{classical: references points }t\in G}=\underbrace{h(f)}_{\text{quantum: no reference to points}}

Representation Theory and ‘sum over points’ arguments, therefore are transferrable and it is precisely these ideas that play a central role in the representation- theoretic approach of Diaconis to analysing the rate of convergence of random walks on finite groups. Once the quantised versions of the various objects and maps used by Diaconis are established — and these were non-trivial tasks — it was largely straightforward to derive and prove the transferred/quantised central tool of Diaconis’ work — the Diaconis-Shahshahani Upper Bound Lemma. The fact that the quantum Upper Bound Lemma is as similar to the classical Upper Bound Lemma as the quantum Peter-Weyl Theorem is to the classical Peter-Weyl is the triumph of this work.

The restriction to finite quantum groups is for two reasons. First of all the classical work that this is building upon is the Diaconis-Shahshahani Theory approach to random walks on finite groups. A caveat must be added: the Diaconis-Shahshahani Theory also applies to compact groups. This is addressed in the chapter on Further Problems. Secondly, the approach to quantising classical notions in this work, requires the isomorphism (A\otimes B)^*=A^*\otimes B^* for spaces A and B and this holds only when A and B are finite dimensional.

This does indeed make the work modest: however on the other hand the application of the Upper Bound Lemma is made more difficult by the fact that for truly quantum groups there must be at least one representation of dimension greater than one. A quantum group with one dimensional representations only is isomorphic to the group ring of a finite (classical) group.

It would be remiss not to declare a deficiency of this work, namely that the upper bounds generated are probably not very sharp — and if sharp, they don’t come with a complementary sharp lower bound. One could argue that the main aim of this study was to prove a Diaconis-Shahshahani Upper Bound Lemma for quantum groups, and while this aim was successful, a more honest appraisal of the work might paraphrase an idiom of calculus and say, in this context at least, that finding upper bounds is mechanics while procuring lower bounds is art — and the author has failed to show a creative side. In particular, failing to present a random walk on a truly quantum group exhibiting the cut-off phenomenon, when this was a key emphasis of the MSc thesis, is a definite black mark. The great hope would be that sharpening these bounds, and, critically, coming up with effective lower bounds would be the subject of future, successful, work.

The primary references for this work are the author’s MSc thesis on random walks on finite groups (available on the arXiv), the paper of Franz & Gohm which introduces random walks on finite quantum groups and the comprehensive book on quantum groups by Timmermann.


The following sections of this first chapter are concerned primarily with discussion of the Gelfand Philosophy. This philosophy leads from Gelfand’s Theorem which states that commutative unital \mathrm{C}^*-algebras are algebras of (continuous) functions on compact, Hausdorff spaces. The philosophy is an invitation to think of noncommutative \mathrm{C}^*-algebras as algebras of functions on quantum spaces. These quantum spaces do not actually exist — and are referred to as virtual objects — yet many questions that can be posed and resolved in the commutative case may also be posed and hopefully resolved in the noncommutative case. It can sometimes be non-trivial to translate classical definitions into the quantised world but in this chapter it is seen that there is a functorial quantisation that often motivates the — correct & well-established in the literature — quantised definitions.

Chapter 2 introduces the general theory of finite quantum groups (as defined by the author); and includes a study of the Haar state. Some examples of finite quantum groups are presented; namely classical groups G, dual groups of classical groups \widehat{G} (which are virtual when G is non-abelian), the Kac-Paljutkin quantum group \mathbb{KP} as well as the one parameter family of quantum groups of Sekine, \mathbb{KP}_n.

Chapter 3 presents the quantisation of discrete-time Markov chains as well as, far more importantly, the quantisation of random walks on finite groups.

In Chapter 4 a distinguished metric, namely the total variation distance, is identified as the conventional measure of closeness to random in this study. As far as the author is aware, not only is this the correct quantisation/generalisation of the classical total variation distance — in that it shares three key features of the classical metric — it has not been studied previously.

Chapter 5 contains the main result or rather tool of this thesis — the Quantum Diaconis-Shahshahani Upper Bound Lemma. Along with the satisfactory definition of the total variation distance, this ensures that the convergence rate for random walks on classical groups (viewed as quantum groups) are precisely the same as before. The Upper Bound Lemma is also applied to a family of random walks on the cocommutative quantum group \widehat{S_n}, some random walks on the `truly quantum’ group of Kac & Paljutkin, as well as a family of random walks on the one-parameter Sekine quantum groups.

Chapter 6 contains some possible avenues of further study.

Most of the original work is concentrated in Chapters 4 and 5 however it would be hoped that all sections contain new perspectives and points of view on previously studied objects.