The relaxation time is not the value of a flow program
Aldous and Fill ask whether the relaxation time of a reversible Markov chain has a characterization as exactly an infimum over flows. It has none of the kind their flow bounds have. The optimal value of a linear or convex quadratic program in flow variables, with coefficients rational in the transition probabilities, lies in the field generated by the transition probabilities, while the relaxation time of the simple random walk on the path with six vertices is $3+\sqrt5$. The relaxation time is nevertheless an optimum of exactly the objective that is dual to minimum congestion: the dual of the congestion program maximises over metrics, and replacing metrics by squared Euclidean distances gives twice the relaxation time.
Authors
- Yitzchak Shmalo (ORCID: https://orcid.org/0000-0002-2886-3049)
Institutions
- Hebrew University of Jerusalem (IL)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-08
- DOI
- https://doi.org/10.5281/zenodo.24064362
- Primary Topic
- Markov Chains and Monte Carlo Methods
- Type
- preprint