Convergence rates of random walk on irreducible representations of finite groups

Abstract

Random walk on the set of irreducible representations of a finite group is investigated. For the symmetric and general linear groups, a sharp convergence rate bound is obtained and a cutoff phenomenon is proved. As related results, an asymptotic description of Plancherel measure of the finite general linear groups is given, and a connection of these random walks with quantum computing is noted.

The main change is an expanded discussion of motivation of these random walks (requested by a referee). A connection with quantum computing is also noted