×

On random random walks. (English) Zbl 0912.60016

The author proves a symmetric analog of a theorem due to Dou and Hildebrand on the expected mixing time of certain random walks on a finite group \(G\) of order \(g\) with uniform distribution \(U\), and derives from this result good bounds on diameters of random directed Cayley graphs. More precisely, extending a spectral analytic method invented by Broder and Shamir the author shows the following Theorem 2: Let \(a>1\), \(\varepsilon>0\) and let \(S\) be a random set of \(k: =[\log^ag]\) elements of \(G\). By \(P_S(x): =| S\cup S^{-1} |^{-1}\) for all \(x\in S\cup S^{-1}\) and \(:=0\) for \(x \notin S\cup S^{-1}\) a random probability measure \(P_S\) is defined whose \(t\)th convolution power will be denoted by \(P^{*t}_S\). Then \(E(\| P_S^{*t} -U\|) \to 0\) as \(g\to \infty\) whenever \(t>(1+ \varepsilon)a (a-1)^{-1} \log_kg\).

MSC:

60B15 Probability measures on groups or semigroups, Fourier transforms, factorization
60G50 Sums of independent random variables; random walks
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C12 Distance in graphs
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] ALDOUS, D. and DIACONIS, P. 1986. Shuffling cards and stopping times. Amer. Math. Monthly 93 333 348. JSTOR: · Zbl 0603.60006
[2] ALON, N. 1995. Personal communication.
[3] ALON, N., BARAK, A. and MANBER, U. 1987. On disseminating information reliably without broadcasting. In Proc. Seventh Internat. Conf. on Distributed Computing Sy stems Z. ICDS 74 81.
[4] ALON, N. and MILMAN, V. D. 1985., isoperimetric inequalities for graphs and supercon1 centrators. J. Combin. Theory Ser. B 38 73 88. · Zbl 0549.05051
[5] ALON, N. and ROICHMAN, Y. 1994. Random Cay ley graphs and expanders. Random Structures Algorithms 5 271 284. · Zbl 0798.05048
[6] BABAI, L. and ERDOS, P. 1982. Representation of group elements as short products. Ann. \" Discrete Math. 12 27 30.
[7] BABAI, L., HETy EI, G., KANTOR, W. M., LUBOTZKY, A. and SERESS, A. 1990. On the diameter of finite groups. Proc. 31st IEEE FOCS 857 865.
[8] BRODER, A. and SHAMIR, E. 1987. On the second eigenvalue of random regular graphs. Proc. 28th IEEE FOCS 286 294.
[9] CHUNG, F. R. K. 1989. Diameters and eigenvalues. J. Amer. Math. Soc. 2 187 196. JSTOR: · Zbl 0678.05037
[10] DIACONIS, P. 1988. Group Representations in Probability and Statistics. IMS, Hay ward, CA. · Zbl 0695.60012
[11] DIACONIS, P. and SALOFF-COSTE, L. 1993. Comparison techniques for random walk on finite groups. Ann. Probab. 21 2131 2156. · Zbl 0790.60011
[12] DIACONIS, P. and SALOFF-COSTE, L. 1995. Nash inequalities for finite Markov chains. · Zbl 0870.60064
[13] DIACONIS, P. and SALOFF-COSTE, L. 1993. Comparison theorems for reversible Markov chains. Ann. Appl. Probab. 3 696 730. · Zbl 0799.60058
[14] DOU, C. and HILDEBRAND, M. 1996. Enumeration and random random walks on finite groups. Ann. Probab. 24 987 1000. · Zbl 0862.60006
[15] FRIEDMAN, J. 1991. On the second eigenvalue and random walks in random d-regular graphs. Combinatorica 11 331 362. · Zbl 0760.05078
[16] FRIEDMAN, J., JOUX, A., ROICHMAN, Y., STERN, J. and TILLICH, J. P. 1995. Most regular graphs are quickly r-transitive.
[17] HILDEBRAND, M. 1994. Random walks supported on random points of n. Probab. Theory Related Fields 100 191 203. · Zbl 0809.60011
[18] HORN, R. and JOHNSON, C. 1990. Topics in Matrix Analy sis. Cambridge Univ. Press.
[19] LUBOTZKY, A. 1994. Discrete Groups, Expanding Graphs and Invariant Measures. Progress in Math. 125. Birkhauser, Boston. \" · Zbl 0826.22012
[20] LUBOTZKY, A. 1995. Cay ley graphs: eigenvalues, expanders and random walks. Survey s in Combinatorics. · Zbl 0835.05033
[21] LUBOTZKY, A., PHILLIPS, R. and SARNAK, P. 1988. Ramanujan graphs. Combinatorica 8 261 277. · Zbl 0661.05035
[22] SARNAK, P. 1990. Some Applications of Modular Forms. Cambridge Tracts in Math. 99. Cambridge Univ. Press. · Zbl 0721.11015
[23] WILSON, D. B. 1995. Random walks on. Preprint. 2
[24] CAMBRIDGE, MASSACHUSETTS 02138 E-MAIL: yuval@math.harvard.edu
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.