2022/06/10 by Stefan Steinerberger, Steinerberger, Stefan, Rekha R. Thomas +1 · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2206.05346
openalex publication_date 2022/06/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G=(V,E) be a d-regular graph on n vertices and let μ0 be a probability measure on V. The act of moving to a randomly chosen neighbor leads to a sequence of probability measures supported on V given by μk+1 = A D-1 μk, where A is the adjacency matrix and D is the diagonal matrix of vertex degrees of G. Ordering the eigenvalues of A D-1 as 1 = λ1 ≥ |λ2| ≥ … ≥ |λn| ≥ 0, it is well-known that the graphs for which |λ2| is small are those in which the random walk process converges quickly to the uniform distribution: for all initial probability measures μ0 and all k ≥ 0, ∑v ∈ V | μk(v) - (1)/(n) |2 ≤ λ22k. One could wonder whether this rate can be improved for specific initial probability measures μ0. We show that if G is regular, then for any 1 ≤ ℓ ≤ n, there exists a probability measure μ0 supported on at most ℓ vertices so that ∑v ∈ V | μk(v) - (1)/(n) |2 ≤ λℓ+12k. The result has applications in the graph sampling problem: we show that these measures have good sampling properties for reconstructing global averages.