On random random walks
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\).
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- Comparison techniques for random walk on finite groups
- Comparison theorems for reversible Markov chains
- Diameters and Eigenvalues
- Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
- Enumeration and random walks on finite groups
- scientific article; zbMATH DE number 44579 (Why is no real title available?)
- scientific article; zbMATH DE number 48345 (Why is no real title available?)
- scientific article; zbMATH DE number 782054 (Why is no real title available?)
- Nash inequalities for finite Markov chains
- On the second eigenvalue and random walks in random d-regular graphs
- Ramanujan graphs
- Random Cayley graphs and expanders
- Random walks supported on random points of Z/nZ
- Shuffling Cards and Stopping Times
- Random walks on amalgams
- Random walks on finite groups with few random generators
- Random walks in tennis
- Mixing properties for hom-shifts and the distance between walks on associated graphs
- The building blocks of random walks
- From random walks to rough paths
- scientific article; zbMATH DE number 3886840 (Why is no real title available?)
- A Random Walk Through Experimental Mathematics
- scientific article; zbMATH DE number 4149301 (Why is no real title available?)
- The diameter of a random Cayley graph of \({\mathbb{Z}}_q\)
- An upper bound on random walks on dihedral groups
- scientific article; zbMATH DE number 1190415 (Why is no real title available?)
- Randomly observed random walks
- scientific article; zbMATH DE number 55669 (Why is no real title available?)
- Rational Random Walks
- scientific article; zbMATH DE number 1827712 (Why is no real title available?)
- On some probability distributions associated with random walks
- scientific article; zbMATH DE number 841532 (Why is no real title available?)
- scientific article; zbMATH DE number 1444753 (Why is no real title available?)
- Random walks on dihedral groups
- On mixing of certain random walks, cutoff phenomenon and sharp threshold of random matroid processes
- Geometry of random Cayley graphs of abelian groups
- An analogue of Aldous's theorem on mixing times of a random walk for complex reflection groups
- Random walks on Cayley graphs of complex reflection groups
- Mini-workshop: Growth and expansion in groups. Abstracts from the mini-workshop held April 7--12, 2024
- The diameter of random Schreier graphs
This page was built for publication: On random random walks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2563947)
