Metropolis on Cayley graphs

Define a one-parameter family \( \mu(p), 0 < p < 1 \) of probability distributions on a finite Cayley graph by:

\( \mu(p)\) is the distribution of \( X(T_p-1) \) , where \(X(i) \) is random walk started at the identity, and \(T_p \) has Geometric(p) distribution.

Take \( \mu(0)\) to be the uniform distribution. Now consider the reversible Markov chain defined by:

the Metropolis chain, based on random walk, with stationary distribution \( \mu(p)\).

This has some relaxation time \( \tau (p)\). Can one prove anything about τ(p) in this general setting? For instance, can one prove
(i) \( \tau (p)\) is monotone decreasing in \( p \)?
(ii) \( \tau (p)\leq C \tau (\infty )\) for some universal C ?
(ii) Some decreasing bound on \( \tau (p)\) in terms of \( \tau (\infty ), p \), number of states and familiar parameters of the graph?

History First written here March 2009, but mentioned in conversation for several years earlier.

Back to Open Problem list