×

zbMATH — the first resource for mathematics

On mixing of certain random walks, cutoff phenomenon and sharp threshold of random matroid processes. (English) Zbl 0983.60036
Geometric random walks are defined as certain Markov chains \(X_t\) on a \(d\)-dimensional space over a finite field. The behaviour of such walks is given by certain random matroid processes. In particular, the mixing time is given by expected stopping time, and the cutoff is equivalent to sharp threshold. A collection of examples and symmetric cases are shown, e.g. lazy random walks on a cube, random walks on a complete and edge-transitive graph, on a coordinate subspace and others. Applications to the coupon collector’s problem are available. The main point of the paper is methodological. The connection between cutoff phenomenon for mixing of random walks and sharp threshold for random matroids and graphs is established. Several open questions regarding the matter are given.

MSC:
60G50 Sums of independent random variables; random walks
05B35 Combinatorial aspects of matroids and geometric lattices
05C80 Random graphs (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aigner, M.: Combinatorial theory. (1979) · Zbl 0415.05001
[2] Aldous, D.; Diaconis, P.: Strong uniform times and finite random walks. Adv. appl. Math. 8, 69-97 (1987) · Zbl 0631.60065
[3] D. Aldous, J. Fill, Reversible Markov chains and random walks on graphs, monograph in preparation, 1996.
[4] A. Astashkevich, I. Pak, Random walks on nilpotent and supersolvable groups, preprint, 1997.
[5] M. Barnabei, A. Brini, G.-C. Rota, The theory of Möbius functions, Usp. Mat. Nauk. 41 (1986) 113–157 (in Russian). · Zbl 0615.05006
[6] Bollobás, B.: Random graphs. (1985) · Zbl 0567.05042
[7] Diaconis, P.: Group representations in probability and statistics. (1988) · Zbl 0695.60012
[8] Diaconis, P.: The cutoff phenomenon in finite Markov chains. Proc. natl. Acad. sci. USA 93, 1659-1664 (1996) · Zbl 0849.60070
[9] Diaconis, P.; Fill, J. A.: Strong stationary times via new form of duality. Ann. probab. 18, 1483-1522 (1990) · Zbl 0723.60083
[10] Diaconis, P.; Graham, R.; Morrison, J.: Asymptotic analysis of a random walk on a hypercube with many dimensions. Random struct. Algorithms 1, 51-72 (1990) · Zbl 0723.60085
[11] Dou, C.; Hildebrand, M.: Enumeration and random random walks on finite groups. Ann. probab. 24, 987-1000 (1996) · Zbl 0862.60006
[12] Erdo\?s, Rényi, On random graphs. I., Publ. Math. Debrecen 6 (1959) 290–297. · Zbl 0092.15705
[13] Feller, W.: An introduction to probability theory and its applications. (1970) · Zbl 0039.13201
[14] Friedgut, E.; Kalai, G.: Every monotone graph property has a sharp threshold. Proc. amer. Math. soc. 124, 2993-3002 (1996) · Zbl 0864.05078
[15] Greenhalgh, A.: A model for random random-walks on finite groups. Combin. probab. Comput. 6, 49-56 (1997) · Zbl 0872.60053
[16] L. Lovász, P. Winkler, Mixing Times, AMS DIMACS Series, Vol. 41, AMS Providence, RI, 1998, pp. 189–204. · Zbl 0908.60065
[17] Margulis, G.: Probabilistic characteristics of graphs with large connectivity. Probl. peredači inform. 10, 101-108 (1974) · Zbl 0322.05147
[18] I. Pak, Random walks on groups: strong uniform time approach, Ph.D. Thesis, Harvard University, 1997.
[19] I. Pak, When and how n choose k, DIMACS Workshops on Randomized Algorithms, AMS, Providence, 1998.
[20] I. Pak, Evolution of random walks on Sn, 1998, in preparation.
[21] Pak, I.: Random walks on finite groups with few random generators. Electron J. Probab. 4, 1-11 (1999) · Zbl 0918.60061
[22] Roichman, Y.: On random random walks. Ann. probab. 24, 1001-1011 (1996) · Zbl 0912.60016
[23] R.P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth & Brooks/Cole, CA, 1986. · Zbl 0608.05001
[24] Talagrand, M.: On Russo’s approximative zero-one law. Ann. probab. 22, 1576-1587 (1994) · Zbl 0819.28002
[25] Whittaker, E. T.; Watson, G. N.: A course of modern analysis. (1927) · JFM 53.0180.04
[26] Wilson, D.: Random random walks on z2n. Probab. theory related fields 108, 441-457 (1997) · Zbl 0896.60034
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.