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 μ_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 μ_0 be the uniform law; and let τ(p) be the relaxation time of the Metropolis chain based on the random walk with stationary law μ_p. Can anything be proved about τ(p) in this generality, for instance (i) that τ(p) is monotone decreasing in p, or (ii) that τ(p) ≤ C τ(∞) for a universal constant C? The symbol τ(∞) 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 − λ_2) and for both readings of τ(∞), namely τ(0) and lim_{p→1} τ(p). We prove, on every finite Cayley graph of degree d with identity e: (1) τ(p) → d as p → 1; (2) for every p, τ(p) ≥ 2 Var(dist(e, X(T_p − 1))) and τ(p) ≥ (1 − p) m (1 − m)/(m − p) with m = μ_p(e); (3) 1/τ(p) = 1/τ(0) − s* p + O(p²) as p → 0, with an explicit constant s* > 0, so that τ(p) > τ(0) for all small p > 0. By (3), item (i) fails on every finite Cayley graph. On the hypercube of dimension d we have τ(0) = d/2, lim_{p→1} τ(p) = d and τ(1/d) ≥ d(d − 1)/15; and on Cayley graphs of bounded degree whose walk eigenvalues other than ±1 are bounded away from ±1, sup_p τ(p) ≥ c (log n)², where n is the number of vertices. Hence (ii) fails under both readings. On the complete graph K_n one has τ(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 τ(p), and its open-ended opening question are not answered. This is an unrefereed note. Unrefereed preprint released for independent mathematical scrutiny. Publication on Zenodo does not constitute peer review. AI-assisted tools supported research, computation, proof development, and manuscript preparation. The author remains responsible for all claims and the final text. Corpus identifier: AMR-096-0008 (D. Aldous, open-problem page "Metropolis on Cayley graphs", March 2009).