A Tale of Two Walks: From Kac to KMP and Back
Qian Chen, Jingcheng Liu, Minglong Qin, Leonard J. Schulman, Fang Song, Penghui Yao, Mingnan Zhao
We reveal an unexpected connection between two interacting particle systems: Kac's walk and the Kipnis-Marchioro-Presutti (KMP) process. We first establish a mixing-time analogue of Aldous's conjecture for the KMP process on general graphs: the mixing time of the $t$-particle process on any connected $d$-vertex graph is at most $O(\log d)$ times the corresponding single-particle mixing time, uniformly in $t$. As an application, we improve the mixing-time bound for coordinate hit-and-run on the $n$-dimensional standard simplex from $\widetilde{O}(n^3)$ [KV26] to $O(n\log n)$, while removing the dependence on the initial distribution. We then show that the twirling channel induced by the parallel Kac's walk on the symmetric subspace can be exactly encoded by a Markov chain on partitions, which naturally lifts to a parallel KMP chain on the complete graph. We prove that $O(\log d+\log(1/\varepsilon))$ repetitions of the parallel Kac's walk suffice to approximate Haar twirling on the symmetric subspace of $(\mathbb{C}^d)^{\otimes t}$ to error $\varepsilon$, uniformly in all $t$. Our main technical contribution is a new structural property of KMP-type dynamics: conditional product structure, which holds for both the standard KMP processes on general graphs and the parallel KMP processes on complete graphs. Conditioned on suitable auxiliary randomness, the evolution of the labeled KMP process factorizes into independent single-particle updates. Combining this structure with an exact coupling, we remove the dependence on the number of particles from the mixing bounds for both unlabeled KMP models. This bypasses the $\log(π_{\min}^{-1})$ dependency from spectral-gap arguments, which is often prohibitively large for many-particle systems. Using this framework, we prove mixing bounds that are sharp up to logarithmic factors for both unlabeled KMP models.
尚无 AI 解读，展示原文摘要