Expanderizing Higher-Order Random Walks

Authors

Vedat Levi Alev, University of Haifa Haifa Israel
Shravas Rao, Portland State University Portland Oregon USAFollow

Published In

Random Structures and Algorithms

Document Type

Article

Publication Date

12-1-2025

Abstract

We study a variant of the down-up (also known as the Glauber dynamics) and up-down walks over an 𝑛-partite simplicial complex, which we call expanderized higher-order random walks—where the sequence of updated coordinates corresponds to the sequence of vertices visited by a random walk over an auxiliary expander graph 𝐻. When 𝐻 is the clique with self-loops on [𝑛], this random walk reduces to the usual down-up walk, and when 𝐻 is the directed cycle on [𝑛], this random walk reduces to the well-known systematic scan Glauber dynamics. We show that whenever the usual higher-order random walks satisfy a log-Sobolev inequality or a Poincaré inequality, the expanderized walks satisfy the same inequalities with a loss of quality related to the two-sided expansion of the auxiliary graph 𝐻. Our construction can be thought of as a higher-order random walk generalization of the derandomized squaring algorithm of Rozenman and Vadhan (RANDOM 2005). We study the mixing times of our expanderized walks in two example cases: We show that when initiated with an expander graph our expanderized random walks have mixing time (i) 𝑂(𝑛 log 𝑛) for sampling uniformly random list colorings of a graph 𝐺 of maximum degree Δ = 𝑂(1) where each vertex has at least 1.809Δ and at most 𝑂(Δ) colors, (ii) 𝑂𝒉( 𝑛 log 𝑛 (1−||J||op)2 ) for sampling the Ising model with a PSD interaction matrix J ∈ ℝ𝑛×𝑛 satisfying ||J||op ≤ 1 and the external field 𝒉 ∈ ℝ𝑛—here the 𝑂(•) notation hides a constant that depends linearly on the largest entry of 𝒉. As expander graphs can be very sparse, this decreases the amount of randomness required to simulate the down-up walks by a logarithmic factor. We also prove some simple results which enable us to argue about log-Sobolev constants of higher-order random walks and provide a simple and self-contained analysis of local-to-global Φ-entropy contraction in simplicial complexes—giving simpler proofs for many pre-existing results.

Rights

Copyright (c) 2025 The Authors

This work is licensed under a Creative Commons Attribution 4.0 International License.

DOI

10.1002/rsa.70032

Persistent Identifier

https://archives.pdx.edu/ds/psu/44312

Citation Details

Alev, V. L., & Rao, S. (2025). Expanderizing Higher‐Order Random Walks. Random Structures & Algorithms, 67(4). Portico.