Answers are grounded in this paper and cite their sources.
Aldous and Fill asked whether the stopping-rule mixing time τ₁⁽²⁾ of a chain obtained from a reversible Markov chain by lumping states is at most an absolute constant times that of the original chain. Hermon and Peres answered the question in the negative: for random walks on graphs of bounded degree, lumping can increase the mixing time by a factor of the order of the logarithm of the number of vertices, and by no more. We consider general reversible chains with n states and show that the largest possible factor $K(n)$ satisfies (n-2)/2≤ K(n)≤ n-1. The upper bound follows from standard inequalities and from the inequality τ₂≤τ₁⁽²⁾ between the relaxation time and the stopping-rule mixing time, for which we give a short proof; the lower bound comes from an explicit random walk on a weighted comb. We also show that lumping increases the mean hitting time of a set A by a factor of at most $n-|A|$, and that this bound cannot be improved by more than a factor of about two.
No takes yet. Share an insight, caveat, or question.
Yitzchak Shmalo (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: