The subgroup algorithm for generating uniform random variables. (English) Zbl 1133.60300
Summary: We suggest a simple algorithm for Monte Carlo generation of uniformly distributed variables on a compact group. Examples include random permutations, Rubik’s cube positions, orthogonal, unitary, and symplectic matrices, and elements of \(\text{GL}_n\) over a finite field. The algorithm reduces to the “standard” fast algorithm when there is one, but many new examples are included.
MSC:
| 60B15 | Probability measures on groups or semigroups, Fourier transforms, factorization |
| 60G50 | Sums of independent random variables; random walks |
References:
| [1] | Varadarajan, Lie Groups, Lie Algebras and Their Representations (1974) |
| [2] | Diaconis, Contemporary Math. 50 pp 183– (1986) · doi:10.1090/conm/050/841092 |
| [3] | DOI: 10.2307/2347989 · doi:10.2307/2347989 |
| [4] | DOI: 10.1137/0717034 · Zbl 0443.65027 · doi:10.1137/0717034 |
| [5] | DOI: 10.1214/aos/1176346703 · Zbl 0559.62002 · doi:10.1214/aos/1176346703 |
| [6] | Sloane, Cryptography: Lecture Notes in Computer Science pp 71– (1983) |
| [7] | Devroye, Non-Uniform Random Variate Generation (1986) · doi:10.1007/978-1-4613-8643-8 |
| [8] | Singmaster, Notes on Rubik’s Magic Cube (1981) |
| [9] | Chevalley, Theory of Lie Groups (1946) |
| [10] | Sims, Computation Problems in Abstract Algebra pp 176– (1970) |
| [11] | DOI: 10.1016/0097-3165(77)90069-3 · Zbl 0354.05003 · doi:10.1016/0097-3165(77)90069-3 |
| [12] | Rouse-Ball, Mathematical Recreations and Essays pp 299– (1962) |
| [13] | DOI: 10.1214/aos/1176343585 · Zbl 0345.62004 · doi:10.1214/aos/1176343585 |
| [14] | Pontryagin, Topological Groups (1966) |
| [15] | DOI: 10.1137/0906011 · Zbl 0552.62052 · doi:10.1137/0906011 |
| [16] | Nijenhuis, Combinatorial Algorithms (1978) |
| [17] | Moses, Tables of Random Permutations pp 4– (1963) · Zbl 0121.14504 |
| [18] | DOI: 10.1214/aoms/1177692644 · Zbl 0248.65008 · doi:10.1214/aoms/1177692644 |
| [19] | Lukacs, Characteristic Functions pp 182– (1970) |
| [20] | DOI: 10.1007/BF02760974 · Zbl 0516.28004 · doi:10.1007/BF02760974 |
| [21] | Knuth, The Art of Computer Programming pp 139– (1981) |
| [22] | Kendall, Geometrical Probability pp 93– (1963) |
| [23] | Kehlet, Math. Scand. 55 pp 152– (1984) · Zbl 0565.22004 · doi:10.7146/math.scand.a-12073 |
| [24] | Hewitt, Abstract Harmonic Analysis II (1970) · Zbl 0213.40103 |
| [25] | Hewitt, Abstract Harmonic Analysis I (1963) · doi:10.1007/978-3-662-00102-8 |
| [26] | Herstein, Topics in Algebra (1964) |
| [27] | Helgason, Groups and Geometric Analysis (1984) |
| [28] | DOI: 10.2307/2346957 · Zbl 0433.65006 · doi:10.2307/2346957 |
| [29] | Halmos, Measure Theory (1950) · doi:10.1007/978-1-4684-9440-2 |
| [30] | Golub, Matrix Computations (1983) |
| [31] | Gleason, Ann. of Math. Stat. 56 pp 193– (1952) |
| [32] | Gilbert, Modern Algebra with Applications pp 81– (1976) |
| [33] | Furst, Proc. 21st FOCS 1 pp 36– (1980) |
| [34] | Fisher, Statistical Tables for Biological Agricultural and Medical Research pp 20– (1938) · JFM 64.1202.02 |
| [35] | DOI: 10.2307/2323334 · Zbl 0601.20005 · doi:10.2307/2323334 |
| [36] | Weyl, The Classical Groups pp 56– (1946) |
| [37] | Eaton, Multivariate Statistics pp 234– (1983) |
| [38] | DOI: 10.2307/2683210 · doi:10.2307/2683210 |
| [39] | Vilenkin, Special Functions and The Theory of Group Representations (1968) · Zbl 0172.18404 |
| [40] | DOI: 10.2307/2045709 · Zbl 0622.60015 · doi:10.2307/2045709 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
