Harmonic Analysis on Finite Groups: Representation Theory, Gelfand Pairs and Markov Chains (Cambridge Studies in Advanced Mathematics, Series Number 108)

Line Up A Deck Of 52 Cards On A Table. Randomly Choose Two Cards And Switch Them. How Many Switches Are Needed In Order To Mix Up The Deck? Starting From A Few Concrete Problems Such As Random Walks On The Discrete Circle And The Finite Ultrametric Space This Book Develops The Necessary Tools For The Asymptotic Analysis Of These Processes. This Detailed Study Culminates With The Case-by-case Analysis Of The Cut-off Phenomenon Discovered By Persi Diaconis. This Self-contained Text Is Ideal For Graduate Students And Researchers Working In The Areas Of Representation Theory, Group Theory, Harmonic Analysis And Markov Chains. Its Topics Range From The Basic Theory Needed For Students New To This Area, To Advanced Topics Such As The Theory Of Green's Algebras, The Complete Analysis Of The Random Matchings, And The Representation Theory Of The Symmetric Group. Tullio Ceccherini-silberstein, Fabio Scarabotti, Filippo Tolli. Includes Bibliographical References And Index. Cover......Page 1 Half-title......Page 3 Series-titles......Page 4 Title......Page 5 Copyright......Page 6 Contents......Page 9 Preface......Page 13 Part I Preliminaries, examples and motivations......Page 17 1.1 Preliminaries and notation......Page 19 1.2 Four basic examples......Page 20 1.3 Markov chains......Page 26 1.4 Convergence to equilibrium......Page 34 1.5 Reversible Markov chains......Page 37 1.6 Graphs......Page 42 1.7 Weighted graphs......Page 44 1.8 Simple random walks......Page 49 1.9 Basic probabilistic inequalities......Page 53 1.10 Lumpable Markov chains......Page 57 2.1 Harmonic analysis on finite cyclic groups......Page 62 2.2 Time to reach stationarity for the simple random walk on the discrete circle......Page 71 2.3 Harmonic analysis on the hypercube......Page 74 2.4 Time to reach stationarity in the Ehrenfest diffusion model......Page 77 2.5 The cutoff phenomenon......Page 82 2.6 Radial harmonic analysis on the circle and the hypercube......Page 85 Part II Representation theory and Gelfand pairs......Page 91 3.1 Group actions......Page 93 3.3 Unitary representations......Page 99 3.4 Examples......Page 103 3.5 Intertwiners and Schur’s lemma......Page 104 3.6 Matrix coefficients and their orthogonality relations......Page 105 3.7 Characters......Page 108 3.8 More examples......Page 112 3.9 Convolution and the Fourier transform......Page 114 3.10 Fourier analysis of random walks on finite groups......Page 119 3.11 Permutation characters and Burnside’s lemma......Page 121 3.12 An application: the enumeration of finite graphs......Page 123 3.13 Wielandt’s lemma......Page 126 3.14 Examples and applications to the symmetric group......Page 129 4 Finite Gelfand pairs......Page 133 4.1 The algebra of bi-K-invariant functions......Page 134 4.2 Intertwining operators for permutation representations......Page 136 4.3 Finite Gelfand pairs: definition and examples......Page 139 4.4 A characterization of Gelfand pairs......Page 141 4.5 Spherical functions......Page 143 4.6 The canonical decomposition of L(X) via spherical functions......Page 148 4.7 The spherical Fourier transform......Page 151 4.8 Garsia’s theorems......Page 156 4.9 Fourier analysis of an invariant random walk on X......Page 159 5.1 Harmonic analysis on distance-regular graphs......Page 163 5.2 The discrete circle......Page 177 5.3 The Hamming scheme......Page 178 5.4 The group-theoretical approach to the Hammming scheme......Page 181 6.1 The Johnson scheme......Page 184 6.2 The Gelfand pair (Sn, Sn-m × Sm) and the associated intertwining functions......Page 192 6.3 Time to reach stationarity for the Bernoulli–Laplace diffusion model......Page 196 6.4 Statistical applications......Page 200 6.5 The use of Radon transforms......Page 203 7.1 The rooted tree Tq,n......Page 207 7.2 The group Aut(Tq,n) of automorphisms......Page 208 7.3 The ultrametric space......Page 210 7.4 The decomposition of the space L(Σn) and the spherical functions......Page 212 7.5 Recurrence in finite graphs......Page 215 7.6 A Markov chain on Σn......Page 218 Part III Advanced theory......Page 223 8.1 Generalities on posets......Page 225 8.2 Spherical posets and regular semi-lattices......Page 232 8.3 Spherical representations and spherical functions......Page 238 8.4 Spherical functions via Moebius inversion......Page 245 8.5 q-binomial coefficients and the subspaces of a finite vector space......Page 255 8.6 The q-Johnson scheme......Page 259 8.7 A q-analog of the Hamming scheme......Page 267 8.8 The nonbinary Johnson scheme......Page 273 9.1 Tensor products......Page 283 9.2 Representations of abelian groups and Pontrjagin duality......Page 290 9.3 The commutant......Page 292 9.4 Permutation representations......Page 295 9.5 The group algebra revisited......Page 299 9.6 An example of a not weakly symmetric Gelfand pair......Page 307 9.7 Real, complex and quaternionic representations: the theorem of Frobenius and Schur......Page 310 9.8 Greenhalgebras......Page 320 9.9 Fourier transform of a measure......Page 330 10.1 Preliminaries on the symmetric group......Page 335 10.2 Partitions and Young diagrams......Page 338 10.3 Young tableaux and the Specht modules......Page 341 10.4 Representations corresponding to transposed tableaux......Page 349 10.5 Standard tableaux......Page 351 10.6 Computation of a Fourier transform on the symmetric group......Page 359 10.7 Random transpositions......Page 364 10.8 Differential posets......Page 374 10.9 James’ intersection kernels theorem......Page 381 11.1 The Gelfand pair (S2n, S2 Sn)......Page 387 11.2 The decomposition of L(X) into irreducible components......Page 389 11.3 Computing the spherical functions......Page 390 11.4 The first nontrivial value of a spherical function......Page 391 11.5 The first nontrivial spherical function......Page 392 11.6 Phylogenetic trees and matchings......Page 394 11.7 Random matchings......Page 396 Appendix 1 The discrete trigonometric transforms......Page 408 Appendix 2 Solutions of the exercises......Page 423 Bibliography......Page 437 Index......Page 449 Starting from a few concrete problems such as random walks on the discrete circle and the finite ultrametric space, this book develops the necessary tools for the asymptotic analysis of these processes. Its topics range from the basic theory needed for students new to this area, to advanced topics such as the theory of Green's algebras, the complete analysis of the random matchings, and a presentation of the presentation theory of the symmetric group. This self-contained, detailed study culminates with case-by-case analyses of the cut-off phenomenon discovered by Persi Diaconis.