PaperlayerView exact revision on arXiv

Source-linked AI summary

Improved Analysis of Higher Order Random Walks and Applications

Vedat Levi Alev, Lap Chi Lau

arXiv:2001.02827v3cs.DSmath.CO

TL;DR

The paper seeks to extend higher-order random-walk techniques to mixing-time analysis for combinatorial Markov chains. It gives an improved eigenvalue bound for down-up walks, with an optimal-order spectral-gap guarantee under a local-expansion condition, and discusses applications to independent-set sampling.

Abstract

from arXiv · show

The motivation of this work is to extend the techniques of higher order random walks on simplicial complexes to analyze mixing times of Markov chains for combinatorial problems. Our main result is a sharp upper bound on the second eigenvalue of the down-up walk on a pure simplicial complex, in terms of the second eigenvalues of its links. We show some applications of this result in analyzing mixing times of Markov chains, including sampling independent sets of a graph and sampling common independent sets of two partition matroids.

1 Introduction

The introduction frames higher-order random walks on simplicial complexes as a route to studying mixing times, with link spectra and local expansion providing the central tools. It reviews earlier spectral-gap results, reductions for checking link conditions, and applications to Markov-chain analysis.

1 Introduction

  • Down-up and up-down walks move among k-dimensional faces and have the uniform distribution on those faces as their stationary distribution.Mixing time is the number of steps needed for the walk’s distribution to approach uniformity.Source: §1 · p. 2

Local Spectral Expanders

  • A pure complex is a γ-local-spectral expander when every link graph up to dimension d−2 has second eigenvalue at most γ.The link graph’s edge weights are proportional to the number of maximal link faces containing each edge.Source: Local Spectral Expanders · p. 2

Kaufman-Oppenheim Theorem

  • Kaufman and Oppenheim’s theorem gives a non-trivial spectral gap for the k-th down-up walk when the complex is a γ-local-spectral expander with γ < 2/k².The cited theorem also concerns the (k−1)-th up-down walk.Source: Kaufman-Oppenheim Theorem · p. 3

Oppenheim’s Trickling Down Theorem

  • Oppenheim’s trickling-down result reduces bounding link-graph eigenvalues across dimensions to checking links at the highest relevant dimension.The reduction is described as essentially lossless in the regime where the Kaufman-Oppenheim theorem applies.Source: Oppenheim’s Trickling Down Theorem · p. 3

Analyzing Mixing Times of Markov Chains

  • Prior work applied these techniques to matroid-basis sampling, obtaining O(d² log n) mixing time and implications for counting bases and basis-exchange expansion.The passage attributes the application to Anari, Liu, Oveis Gharan, and Vinzant.Source: Analyzing Mixing Times of Markov Chains · p. 4
  • The approach has a scope boundary: the cited matroid analysis does not extend beyond matroids, and many considered problems fail its required link-eigenvalue condition.The theorem requires λ2(Gα)=O(1/d²) for every face up to dimension d−2.Source: Analyzing Mixing Times of Markov Chains · p. 4

1.1 Main Result

Theorem 1.5 gives an improved eigenvalue bound for higher-order random walks on pure simplicial complexes. Its refinements yield mixing-time and spectral-gap applications, including for longer random walks.

1.1 Main Result

  • Theorem 1.5 quantitatively generalizes the criterion that connected lower-dimensional face links imply gallery connectivity.Source: §1.1 · p. 5
  • An Ω(1/k) spectral gap for the k-th down-up walk follows when X is an O(1/k)-local-spectral expander, improving the O(1/k²) requirement and matching the universal O(1/k) upper bound up to constants.Source: §1.1 · p. 5
  • Using different bounds γj for links of different dimensions is useful for analyzing Markov chains.Source: §1.1 · p. 5
  • Theorem 1.5 also gives a tighter spectral-gap bound for certain longer random walks, which are useful in coding theory and agreement testing.Source: §1.1 · p. 5
  • If the highest-dimensional unweighted link graphs satisfy λ2(Gβ) ≤ 1/(d + 1), Corollary 1.6 concludes that P▽d is fast mixing.Source: §1.1 · p. 5

1.2 Applications

The applications use simplicial-complex walks to study mixing in combinatorial sampling, high-dimensional expander constructions, and longer walks. They include refined independent-set results, a conditional fast-mixing result for common independent sets, and improved bounds for longer walks.

1.2.1 Sampling Independent Sets of Fixed Size

  • The independent-set walk mixes under a refined condition involving the minimum eigenvalue of the graph adjacency matrix, allowing larger sets when that eigenvalue is smaller than the maximum degree.The passages state that the known bound |λmin(AG)| ≤ ∆ recovers the earlier fast-mixing regime, while some graph classes have |λmin(AG)| smaller than ∆.Source: §1.2.1 · p. 6

1.2.2 Sampling Common Independent Sets in Two Partition Matroids

  • For two partition matroids with no pair of elements sharing a block in both, the common-independent-set walk is fast mixing when k ≤ r/3.Here r is the size of a common independent set; the result applies to the down-up walk on the matroid intersection complex.Source: §1.2.2 · p. 6

1.2.3 Sampling Independent Sets from Hardcore Distributions

  • Theorem 1.5 yields fast mixing for independent sets sampled from the hardcore distribution up to the uniqueness threshold, including graphs of unbounded maximum degree.The cited result uses link-dependent bounds γj = Θ(1/(n−j)); the different bounds across link dimensions are important to the conclusion.Source: §1.2.3 · p. 7

1.2.4 Combinatorial Constructions of High Dimensional Expanders

  • Theorem 1.5 derives the higher-order-walk bound in Item (3) from the link spectral property in Item (2), slightly improving the prior bound and considerably simplifying its analysis.This answers affirmatively whether Item (2) alone suffices for the fast-mixing result.Source: §1.2.4 · p. 8

1.2.5 Longer Random Walks and Other Applications

  • The paper improves the bound for the a-th up-down walk through dimension b when X is a γ-local-spectral expander and 0 ≤ a < b ≤ d−1.The walk moves from an a-dimensional face up to a uniformly sampled b-dimensional face containing it, then down to a uniformly sampled a-dimensional subset.Source: §1.2.5 · p. 8
  • The authors suggest Corollary 1.12 may aid construction of double samplers from Ramanujan complexes under a weaker expansion assumption.They present this as a potential application, not a demonstrated result.Source: §1.2.5 · p. 8

1.3 Related Work

Prior work developed spectral and combinatorial tools for higher-order walks and applied them to expansion, testing, coding, and approximation. The paper’s simplicial-complex approach bounds the second eigenvalue directly, differing from common mixing-time methods in what they analyze.

Higher Order Random Walks and Applications

  • Higher-order-walk research developed local-spectral expansion alongside skeleton and colorful expansion, then used these notions to prove mixing and construct agreement testers.The cited work also connects these methods to PCP constructions, coding, and agreement testing.Source: Higher Order Random Walks and… · p. 9
  • Other high-dimensional-expander definitions support approximate characterization of walk eigenvalues and eigenvectors, while swap or complement walks have been applied to constraint-satisfaction approximation and agreement testing.The passages also describe coding applications using double samplers and swap walks.Source: Higher Order Random Walks and… · p. 9

Analyzing Mixing Times of Markov Chains

  • Mixing-time analyses also use coupling, canonical paths or multicommodity flow, geometric methods, and analytical inequalities such as modified log-Sobolev and Nash inequalities.The cited examples include sampling graph colorings, perfect matchings, matroid bases, and points in convex bodies.Source: Analyzing Mixing Times of Markov Chains · p. 9
  • The paper’s linear-algebraic simplicial-complex approach directly bounds the second eigenvalue, unlike coupling’s comparison of processes or canonical-path and geometric methods’ bounds on underlying expansion.Analytical inequalities can yield sharp mixing bounds when applicable, but the text says they are more difficult to apply and less widely applicable.Source: Analyzing Mixing Times of Markov Chains · pp. 9–10

2.1 Linear Algebra

The section establishes notation for probability-weighted vector spaces and operators, then collects spectral facts used in later arguments. It also defines weighted graph random walks and reversibility.

Vectors and Inner-Products

Matrices and Eigenvalues

  • The section defines weighted graph adjacency, degree, and random-walk matrices, and identifies the latter as row-stochastic.For undirected weighted graphs, the random walk is self-adjoint with respect to its degree-proportional stationary distribution and is therefore reversible.Source: Matrices and Eigenvalues · p. 10
  • It introduces singular values, self-adjointness, positive semidefinite order, and eigenvalue notation for operators on probability-weighted spaces.For self-adjoint operators, eigenvalues are real and eigenvectors can be chosen orthonormal in the corresponding weighted inner product.Source: Matrices and Eigenvalues · pp. 10–11
  • The later proofs rely on spectrum preservation for AB and BA, eigenvalue monotonicity under operator order, and interlacing theorems.The section names Cauchy and Weyl interlacing.Source: Matrices and Eigenvalues · p. 11

2.2 Simplicial Complexes

The section defines pure simplicial complexes and their probability weights, then constructs links with induced conditional distributions and associated link graphs. These definitions set up the local spectral objects used in the paper.

2.2 Simplicial Complexes

  • A simplicial complex is downward closed; a pure d-dimensional complex has every maximal face of dimension d.A face’s dimension is its cardinality minus one, and X(j) denotes the faces of dimension j.Source: §2.2 · p. 11

Weighted Simplicial Complexes

  • A weighted simplicial complex assigns a probability distribution to its top-dimensional faces and obtains distributions on lower-dimensional faces by taking marginals.Equivalently, sample a top-dimensional face and then a uniformly random subset of the desired dimension.Source: Weighted Simplicial Complexes · p. 12

Links and Graphs

  • A face’s link consists of faces extending it, with induced probability distributions defined by conditioning on containment of that face.The graph of a link is its 1-skeleton, with edge weights given by the corresponding conditional face probabilities.Source: Links and Graphs · p. 12
  • When the top-face distribution is uniform, the edge weighting in the graph of a codimension-two link is uniform.The text notes that this observation is used in Section 4.Source: Links and Graphs · p. 12

2.3 Local Spectral Expanders

The section defines link-graph random walk matrices and uses their second eigenvalues to express local spectral expansion. Oppenheim’s theorem relates eigenvalues across links under a balanced-weight condition.

Random Walk Matrices

  • Each link graph has a random walk matrix formed from its adjacency matrix and diagonal degree matrix; it is self-adjoint in the weight-defined inner product and has largest eigenvalue 1.Source: Random Walk Matrices · pp. 12–13

Local Spectral Expanders and Oppenheim’s Theorem

  • A pure complex is a γ-local-spectral expander when its link-graph second eigenvalues are bounded by γ across the specified dimensions.Source: Local Spectral Expanders and… · p. 13
  • Oppenheim’s theorem relates the second eigenvalue of a lower-dimensional link graph to that of a higher-dimensional link when the complex has balanced weights.For the paper’s weight function, the balance constant is c_k = 1/(k + 2).Source: Local Spectral Expanders and… · p. 13
  • An inductive corollary extends the link-eigenvalue relation when the relevant link graphs are connected across dimensions.Source: Local Spectral Expanders and… · p. 13

2.4 Higher Order Random Walks

The section defines adjacent-face up and down operators and builds higher-order walks from their compositions. These walks can be viewed as two-step moves on weighted bipartite graphs, with longer walks connecting nonadjacent face dimensions.

Up and Down Operators

  • The up and down operators act between functions on adjacent face dimensions and are adjoints under the corresponding weight-defined inner products.Their names follow right-action notation: as random walks, the up operator describes a down-move and the down operator an up-move.Source: Up and Down Operators · p. 14

Down-Up Walk, Up-Down Walk, and Non-Lazy Up-Down Walk

  • The down-up and up-down walks are compositions of these operators, share the stated stationary distribution, and are self-adjoint; the up-down walk is positive semidefinite.The non-lazy up-down walk is the up-down walk conditioned on not looping.Source: Down-Up Walk, Up-Down Walk, and… · pp. 14–15
  • A down-up step drops an element uniformly from a higher-dimensional face, then samples a containing face according to the prescribed weights.The walk is represented as a two-step random walk on a weighted bipartite graph between adjacent face dimensions.Source: Down-Up Walk, Up-Down Walk, and… · p. 15
  • For uniform face weights, the walks reduce to the forms described in the introduction.Source: Down-Up Walk, Up-Down Walk, and… · p. 15

Longer Random Walks

  • A longer up-down walk moves between dimensions a and b through the operator composition, and corresponds to two steps on a weighted bipartite graph joining those dimensions.The bipartite edge weights are proportional to the weights of the b-dimensional faces.Source: Longer Random Walks · p. 15

2.5 Mixing Times of Markov Chains

The section defines mixing time through distance from a chain’s stationary distribution and gives a spectral mixing-time bound. It also states that approximate sampling and counting are equivalent for self-reducible problems, connecting the paper’s independent-set samplers to approximate counting.

2.5 Mixing Times of Markov Chains

  • Mixing time is the least number of steps for a walk’s distribution to be ε-close to its stationary distribution in ℓ1 distance.The section invokes a spectral mixing-time bound using the second-largest singular value of the transition matrix.Source: §2.5 · pp. 15–16

Approximate Sampling and Approximate Counting

  • An FPRAUS approximates the uniform distribution over a set in polynomial time in input size and log(1/δ), while an FPRAS approximates its count in polynomial time in input size, 1/ε, and log(1/δ).Source: Approximate Sampling and Approximate… · p. 16
  • For self-reducible sets in NP, an FPRAS exists if and only if an FPRAUS exists.The paper applies this equivalence to conclude that its approximate independent-set samplers also yield approximate counting.Source: Approximate Sampling and Approximate… · p. 16

3 Eigenvalue Bounds for Higher Order Random Walks

The section bounds higher-order walk eigenvalues using the second eigenvalues of links and develops related results for the full spectrum and longer walks. Its proofs use induction and link-walk identities, while a conductance argument establishes a near-tight bound for the top-dimensional walk.

3 Eigenvalue Bounds for Higher Order Random Walks

  • Theorem 3.1 bounds the second eigenvalue of a down-up walk in terms of local link eigenvalues, extending the gallery-connectivity criterion to weighted complexes.The result applies to pure weighted simplicial complexes; the text identifies gallery connectivity with the second eigenvalue being below 1.Source: §3 · pp. 16–17
  • Theorem 3.2 extends the eigenvalue result to the entire spectrum: for each r, the number of eigenvalues above its stated threshold is at most |X(r)|.Theorem 3.1 is the r = −1 special case.Source: §3 · p. 17

3.4 Proof of Proposition 3.3

  • Proposition 3.3 gives a near-tight bound for the top-dimensional down-up walk, proved by bounding conductance using the faces containing a vertex.From such a face, leaving that set in one step requires dropping the vertex, with probability 1/(d + 1).Source: §3 · p. 17, §3.4 · p. 24

3 Eigenvalue Bounds for Higher Order Random Walks

  • Combining Theorem 3.1 with Oppenheim’s corollary bounds the top-dimensional down-up walk using only the maximum second eigenvalue of link graphs in dimension d −2.Source: §3 · p. 17

3.3 Proof of Corollary 3.5

  • For a γ-local-spectral expander, Corollary 3.5 gives an eigenvalue bound for walks spanning dimensions a to b.The proof uses a bound on singular values of products of row-stochastic matrices and telescoping cancellations.Source: §3 · pp. 17–18, §3.3 · pp. 22–23

3.1 Proof of Theorem 3.1

  • The proof of Theorem 3.1 proceeds by induction, using a lemma that bounds the difference between non-lazy up-down and down-up walks through second eigenvalues of links.The proof follows the approach of [DDFH18, Theorem 5.5] while establishing a stronger inequality.Source: §3.1 · p. 18

3.1.1 Proof of Lemma 3.6

  • The Garland method decomposes higher-order walk matrices into link random walk matrices, and the proof applies identities for restrictions of functions to links.Source: §3.1.1 · p. 19

3.2 Proof of Theorem 3.2

  • Theorem 3.2 is proved by induction on the walk dimension, using rank and eigenvalue-count arguments for the base case and induction step.Source: §3.2 · pp. 21–22

4 Analyzing Mixing Times of Markov Chains

The section applies higher-order walks to independent-set sampling, using bounds on link eigenvalues to analyze mixing. For graphs with smaller minimum-adjacency eigenvalue magnitude, the resulting condition permits larger independent sets than the general maximum-degree bound.

4 Analyzing Mixing Times of Markov Chains

  • The applications analyze natural down-up walks for sampling fixed-size independent sets and common independent sets of two partition matroids.For independent sets, the complex contains independent sets of size at most k and has the uniform distribution on its size-k faces.Source: §4 · p. 24, §4.1 · p. 24

4.1 Independent Sets

  • For k ≤ n/(∆ + |λmin(AG)|), the down-up walk on the independent-set complex is covered by the stated mixing-time result.The theorem’s bound can permit larger independent sets when |λmin(AG)| is smaller than ∆; the general bound recovers fast mixing for k ≤ n/(2∆).Source: §4.1 · p. 25

4.1.1 Proof of Theorem 1.7

  • For each S ∈ IG,k with |S| ≤ k − 2, the link graph GS has random-walk matrix MS with λ2(MS) < 1; when |S| = k − 2, λ2(MS) ≤ 1/k.Source: §4.1.1 · p. 25

4.1.2 Proof of Lemma 4.2

  • For |S| ≤ k − 2, the link support graph is connected when k ≤ |V|/(∆ + 1), giving λ2(MS) < 1.The proof establishes the stronger property that every two vertices in the support graph have a path of length at most two.Source: §4.1.2 · p. 26

4.1.3 Proof of Lemma 4.3

  • For |S| = k − 2, the link-walk eigenvalue bound λ2(MS) ≤ 1/k follows under k ≤ |V|/(∆ + |λmin(AG)|), using interlacing arguments.At this link dimension the walk matrix agrees with that of the unweighted support graph.Source: §4.1.3 · pp. 26–27

4.2 Matroid Intersection

The section analyzes the down-up walk for sampling size-k common independent sets of two matroids. For partition matroids satisfying the stated block condition, it bounds the walk’s second eigenvalue when k ≤ r/3.

4.2 Matroid Intersection

  • For two partition matroids with a common independent set of size r and no pair of elements in the same block of both matroids, k ≤ r/3 gives λ2(MS) ≤ 1/k on links with |S| = k − 2.This is the spectral condition used for the upper bound on the down-up walk’s second eigenvalue.Source: §4.2 · p. 28, §4.2.3 · p. 30

4.2.1 Proof of Theorem 1.8

  • Any common independent set S with |S| < r/2 extends to a larger common independent set, so the size-k complex is pure when k ≤ r/2.The proof finds elements extendable in each matroid; the two eligible subsets intersect when |S| < r/2.Source: §4.2.1 · p. 29

4.2.2 Proof of Lemma 4.5

  • For k < r/2 − 1, links with |S| ≤ k − 2 have λ2(MS) < 1 because their support graphs are connected.The proof represents the support graph as the complement of the line graph of a bipartite graph, then establishes paths of length at most two.Source: §4.2.2 · pp. 29–30

Related papers

Loading 2001.02827v3…