On random random walks (Q2563947)

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\).