Probability in the Engineering and Informational Sciences


The Subgroup Algorithm for Generating Uniform Random Variables

Persi Diaconisa1 and Mehrdad Shahshahania2

a1 Department of Statistics Stanford University Stanford, California

a2 Jet Propulsion Laboratory California Institute of Technology Pasadena, California


We suggest a simple algorithm for Monte Carlo generation of uniformly distributed variables on a compact group. Example include random permutations, Rubik's cube positions, orthogonal, unitary, and symplectic matrices, and elements of GLn over a finite field. the algorithm reduces to the “standard” fast algorithm when there is one, but many new example are included.