Home | Current | Past volumes | About | Login | Notify | Contact | Search
 Probability Surveys > Vol. 2 (2005) open journal systems 


A survey of results on random random walks on finite groups

Martin V. Hildebrand, University at Albany, State University of New York


Abstract
A number of papers have examined various aspects of ``random random walks'' on finite groups; the purpose of this article is to provide a survey of this work and to show, bring together, and discuss some of the arguments and results in this work. This article also provides a number of exercises. Some exercises involve straightforward computations; others involve proving details in proofs or extending results proved in the article. This article also describes some problems for further study.

AMS 2000 subject classifications: Primary 60-02; secondary 60B15.

Keywords: random walk, finite group, Upper Bound Lemma, Fourier analysis.

Creative Common LOGO

Full Text: PDF


Hildebrand, Martin V., A survey of results on random random walks on finite groups, Probability Surveys, 2, (2005), 33-63 (electronic).

References

[1]   Chung, F., Diaconis, P., and Graham, R. A random walk problem arising in random number generation. Ann. Probab. 15 (1987), 1148-1165. MR893921

[2]   Dai, J., and Hildebrand, M. Random random walks on the integers mod n. Statist. Probab. Letters 35 (1997), 371-379. MR1483024

[3]   Diaconis, P. Group Representations in Probability and Statistics. Institute of Mathematical Statistics, 1988.

[4]   Diaconis, P., and Shahshahani, M. Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Geb. 57 (1981), 159-179. MR626813

[5]   Dou, C. Studies of random walks on groups and random graphs. Ph.D. thesis, Department of Mathematics, Massachusetts Institute of Technology, 1992.

[6]   Dou, C., and Hildebrand, M. Enumeration and random walks on finite groups. Ann. Probab. 24 (1996), 987-1000. MR1404540

[7]   Erdʺo   s, P., and Rényi. Probabilistic methods in group theory. J. Analyse Math. 14 (1965), 127-138. MR202831

[8]   Feller, W. An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd ed. John Wiley, 1968.

[9]   Feller, W. An Introduction to Probability Theory and Its Applications, Vol. 2, 2nd ed. John Wiley, 1971.

[10]   Greenhalgh, A. Random walks on groups with subgroup invariance properties. Ph.D thesis, Department of Mathematics, Stanford University, 1989.

[11]   Greenhalgh, A. On a model for random random-walks on finite groups. Unpublished manuscript, 1990.

[12]   Greenhalgh, A. A model for random random-walks on finite groups. Combin. Probab. Comput. 6 (1997), 49-56. MR1436719

[13]   Hildebrand, M. Rates of convergence of some random processes on finite groups. Ph.D. thesis, Department of Mathematics, Harvard University, 1990.

[14]   Hildebrand, M. Random walks supported on random points of ∕n Probab. Theor. Related Fields 100 (1994), 191-203. MR1296428

[15]   Hildebrand, M. Random lazy random walks on arbitrary finite groups. J. Theoret. Probab. 14 (2001), 1019-1034. MR1860086

[16]   Hildebrand, M. A note on various holding probabilities for random lazy random walks on finite groups. Stat. Probab. Letters 56 (2002), 199-206. MR1881174

[17]   McCrea, W., and Whipple, F. Random paths in two and three dimensions. Proc. Royal Soc. Edinburgh 60 (1940), 281-298. MR2733

[18]   Pak, I. Random walks on finite groups with few random generators. Electron. J. Probab. 4 (1999), 1-11.

[19]   Polya, G. Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Strassennetz. Math. Ann. 84 (1921), 149-160.

[20]   Roichman, Y. On random random walks, Ann. Probab. 24 (1996), 1001-1011. MR1404541

[21]   Ross, S. Introduction to Probability Models, 7th edition. Academic Press, 2000.

[22]   Saloff-Coste, L. Random walks on finite groups. In Probability on Discrete Structures, H. Kesten, editor, Springer, 2004. MR2023649

[23]   Serre. J.-P. Linear representations of finite groups. Springer-Verlag, 1977.

[24]   Simon, B. Representations of finite and compact groups. American Mathematical Society, 1996.

[25]   Terras, A. Fourier analysis on finite groups and applications. Cambridge University Press, 1999.

[26]   Wilson, D. Random random walks on 2d. Probab. Theory Related Fields 108 (1997), 441-457. MR1465637




Home | Current | Past volumes | About | Login | Notify | Contact | Search

Probability Surveys. ISSN: 1549-5787