Enumeration and random random walks on finite groups

Abstract

This paper examines random walks on a finite group G and finds upper bounds on how long it takes typical random walks supported on $(\log|G|)^a$ elements to get close to uniformly distributed on G. For certain groups, a cutoff phenomenon is shown to exist for these typical random walks. A variation of the upper bound lemma of Diaconis and Shahshahani and some counting arguments related to a group equation are used to get the upper bound. A further example which uses this variation is discussed.