Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-26T17:25:25.431Z Has data issue: false hasContentIssue false
  • English
  • Français

The Subgroup Algorithm for Generating Uniform Random Variables

Published online by Cambridge University Press:  27 July 2009

Persi Diaconis  and
Mehrdad Shahshahani
Persi Diaconis
Affiliation:
Department of StatisticsStanford University Stanford, California
Mehrdad Shahshahani
Affiliation:
Jet Propulsion Laboratory California Institute of Technology Pasadena, California
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 1 , Issue 1 , January 1987 , pp. 15 - 32
Copyright
Copyright © Cambridge University Press 1987

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Anderson, T. W. and Olkin, I. (1985). Generation of random orthogonal matrices. Technical Report No. 6, Department of Statistics, Stanford University. To appear, SIAM Jour. Sci. Statist. Comput.Google Scholar
Asimov, D. (1983). The grand tour. SIAM Jour. Sci. Statist. Comput. 6: 128–143.CrossRefGoogle Scholar
Bondar, J. V. (1976). Borel cross-sections and maximal invariants. Ann. Statist. 4: 866–877.CrossRefGoogle Scholar
Calabi, E. and Wilf, H. S. (1977). On the sequential and random selection of subspaces over a finite field. Jour. Combin. Th. 22: 107–109.CrossRefGoogle Scholar
Chevalley, C. (1946). Theory of Lie Groups. Princeton University Press, Princeton, New Jersey, Chapter 1.Google Scholar
Devroye, L. (1986). Non-Uniform Random Variate Generation. Springer-Verlag, New York, Chapters 9 and 13.CrossRefGoogle Scholar
Diaconis, P. and Freedman, D. (1984). Asymptotics of graphical projection pursuit. Ann. Stat. 12: 793–815.CrossRefGoogle Scholar
Diaconis, P. and Mallows, C. (1984). The trace of Haar measure. Unpublished manuscript.Google Scholar
Diaconis, P. and Newman, C. (1984). The elements of a random orthogonal matrix are approximately normal. Unpublished manuscript.Google Scholar
Diaconis, P. and Shahshahani, M. (1986a). On square roots of the uniform distribution on compact groups. Proc. Amer. Math. Soc. 98: 341–348.CrossRefGoogle Scholar
Diaconis, P. and Shahshahani, M. (1986b). Products of random matrices as they arise in the study of random walks on groups. Contemporary Math. 50: 183–195.CrossRefGoogle Scholar
Dudewicz, E. J. and Dann, R. E. (1972). Equally likely dice sums do not exist. Amer. Statistician 26: #4, 41–42.Google Scholar
Eaton, M. L. (1983). Multivariate Statistics. Wiley, New York, p. 234.Google Scholar
Eidswick, J. A. (1986). Cubelike puzzles—what are they and how do you solve them? Amer. Math. Monthly 93: 157–176.Google Scholar
Fisher, R. A. and Yates, F. (1938). Statistical Tables for Biological Agricultural and Medical Research. Oliver and Boyd, London, p. 20.Google Scholar
Furst, M., Hopcroft, J., and Luks, E. (1980). Polynomial time algorithms for permutation groups. Proc. 21st FOCS 1, 36–41.Google Scholar
Gilbert, W. J. (1976). Modern Algebra with Applications. Wiley, New York, p. 81.Google Scholar
Gleason, A. M. (1952). Groups without small subgroups. Ann. of Math. Stat. 56: 193–212.Google Scholar
Golub, G. and Van, Loan C. (1983). Matrix Computations. Johns Hopkins, Baltimore, Maryland, Chaps. 11, 12.Google Scholar
Halmos, P. (1950). Measure Theory. Van Nostrand, New York.CrossRefGoogle Scholar
Heiberger, R. M. (1978). Generation of random orthogonal matrices. Applied Statistics 27: 199–206.CrossRefGoogle Scholar
Helgason, S. (1984). Groups and Geometric Analysis. Academic Press, New York, Chapter 1.Google Scholar
Herstein, I. N. (1964). Topics in Algebra. Blaisdell, Waltham, Massachusetts, Chap. 2.Google Scholar
Hewitt, E. and Ross, K. (1963). Abstract Harmonic Analysis I. Springer-Verlag, Berlin.Google Scholar
Hewitt, E. and Ross, K. (1970). Abstract Harmonic Analysis II. Springer-Verlag, Berlin.Google Scholar
Kehlet, E. T. (1984). Cross sections for quotient maps of locally compact groups. Math. Scand. 55: 152–160.CrossRefGoogle Scholar
Kendall, M. G. and Moran, P. A. P. (1963). Geometrical Probability. Griffin, London, p. 93.Google Scholar
Knuth, D. (1981). The Art of Computer Programming, Vol. II, 2nd ed.Addison-Wesley, Reading, Massachusetts, p. 139–141.Google Scholar
Kupka, J. (1983). Strong liftings with application to measurable cross sections of locally compact groups. Israel Jour. Math. 44: 243–261.CrossRefGoogle Scholar
Lukacs, E. (1970). Characteristic Functions, 2nd ed.Griffin, London, p. 182–183.Google Scholar
Marsaglia, G. (1972). Choosing a point from the surface of a sphere. Ann. Math. Statist. 43: 645–646.CrossRefGoogle Scholar
Moses, L. E. and Oakford, R. A. (1963). Tables of Random Permutations. Stanford University Press, Stanford, California, p. 4–5.Google Scholar
Nijenhuis, A. and Wilf, H. S. (1978). Combinatorial Algorithms, 2nd ed.Academic Press, New York.Google Scholar
Odlyzko, A. (1986). Personal communication.Google Scholar
Pontryagin, (1966). Topological Groups, 2nd ed.Gordon and Breach, New York, Chapter 11.Google Scholar
Rouse-Ball, W. W. (1962). Mathematical Recreations and Essays, 11th ed.Macmillan, New York, p. 299.Google Scholar
Sims, C. (1970), Computation Problems in Abstract Algebra (John, Leech, ed.). Pergamon Press, New York, p. 176–177.Google Scholar
Singmaster, D. (1981). Notes on Rubik's Magic Cube. Enslow Publishers, Hillside, New Jersey.Google Scholar
Sloane, N. J. A. (1983). Encrypting by random relations. In Cryptography: Lecture Notes in Computer Science, Vol. 149, (Beth, T., ed). Springer-Verlag, Berlin, p. 71–128.CrossRefGoogle Scholar
Stewart, G. W. (1980). The efficient generation of random orthogonal matrices with an application to condition estimators. SIAM Jour. Numer. Anal. 17: 403–409.CrossRefGoogle Scholar
Tanner, M. A. and Thisted, R. (1982). A remark on AS127. Generation of random orthogonal matrices. Applied Statistics 31: 190–192.CrossRefGoogle Scholar
Varadarajan, V. S. (1974). Lie Groups, Lie Algebras and Their Representations. Prentice Hall, Englewood Cliffs, New Jersey.Google Scholar
Vilenkin, N. J. (1968). Special Functions and The Theory of Group Representations. American Mathematical Society, Providence, Rhode Island, Chapter 9.CrossRefGoogle Scholar
Wedderburn, R. W. M. (1975). Generating random rotations. Research Report, Rothamsted Experimental Station.Google Scholar
Weyl, H. (1946). The Classical Groups. Princeton University Press, Princeton, New Jersey, Chapter 7, p. 56.Google Scholar