On Aldous's Question about the Metropolis Chain on Cayley Graphs: Non-Monotonicity of the Relaxation Time

The list of open problems of D. Aldous contains the following question, dated March 2009. On a finite Cayley graph let \(\mu_p\), \(0<p<1\), be the law of \(X(T_p-1)\), where \(X\) is the random walk started at the identity and \(T_p\) is a geometric time with parameter \(p\); let \(\mu_0\) be the uniform law; and let \(\tau(p)\) be the relaxation time of the Metropolis chain based on the random walk with stationary law \(\mu_p\). Can anything be proved about \(\tau(p)\) in this generality, for instance (i) that \(\tau(p)\) is monotone decreasing in \(p\), or (ii) that \(\tau(p)\le C\,\tau(\infty)\) for a universal constant \(C\)? The symbol \(\tau(\infty)\) is not defined in the source. We give a partial answer: items (i) and (ii), as literally posed, have negative answers, for the relaxation time \(1/(1-\lambda_2)\) and for both readings of \(\tau(\infty)\), namely \(\tau(0)\) and \(\lim_{p\to1}\tau(p)\). We prove, on every finite Cayley graph of degree \(d\) with identity \(e\): (1) \(\tau(p)\to d\) as \(p\to1\); (2) for every \(p\), \(\tau(p)\ge2\operatorname{Var}\bigl(\operatorname{dist}(e,X(T_p-1))\bigr)\) and \(\tau(p)\ge(1-p)m(1-m)/(m-p)\) with \(m=\mu_p(e)\); (3) \(1/\tau(p)= 1/\tau(0)-s^*p+O(p^2)\) as \(p\to0\), with an explicit constant \(s^*>0\), so that \(\tau(p)>\tau(0)\) for all small \(p>0\). By (3), item (i) fails on every finite Cayley graph. On the hypercube of dimension \(d\) we have \(\tau(0)=d/2\), \(\lim_{p\to1}\tau(p)=d\) and \(\tau(1/d)\ge d(d-1)/15\); and on Cayley graphs of bounded degree whose walk eigenvalues other than \(\pm1\) are bounded away from \(\pm1\), \(\sup_p\tau(p)\ge c(\log n)^2\), where \(n\) is the number of vertices. Hence (ii) fails under both readings. On the complete graph \(K_n\) one has \(\tau(p)=(n-1)(1+(n-2)p)/(n-p)\), which is strictly increasing; this is a corollary of a known formula (Liu; Diaconis and Saloff-Coste; Aldous and Fill), and since it already contradicts item (i) and, under the first reading, item (ii), the question that was intended may differ from the literal one. The methods are standard. The third item of the source, which asks for a decreasing bound on \(\tau(p)\), and its open-ended opening question are not answered. This is an unrefereed note.