连通图加边后随机游走mixing time的变化及是否增大的技术问询

Great question—your intuition that adding edges usually reduces mixing time makes total sense. After all, edges create shortcuts, boost connectivity, and generally help random walkers spread out faster across the graph. But surprisingly, there are adversarial edge additions that can actually make the mixing time longer! Let's break this down clearly.

1. Why Your Intuition Is Mostly Correct #

In most practical cases, adding edges to a connected graph $G$ will either decrease the mixing time or leave it unchanged. Here's why:

• Adding edges typically increases the graph's conductance (a critical metric for mixing time—higher conductance means the walker can move between subsets of nodes more easily, leading to faster mixing).
• New edges give the walker more paths to explore, cutting down the time it takes to reach distant parts of the graph.
• For common graph families like expanders, grids, or trees, adding any edge will strictly reduce mixing time (trees, for example, have the worst possible mixing time for their size—any edge addition creates a cycle and immediately speeds up the walker).

2. The Surprising Counterexample: Adversarial Edge Addition #

Yes, you can add an edge and make mixing time worse. A classic scenario involves creating a "trapping" structure that diverts the walker away from under-explored parts of the graph:

Imagine starting with a graph $G$ made of two components:

• A large cycle $C$ (length $N$, which has slow mixing because the walker has to loop around to reach distant nodes)
• A small, dense clique $K$ (size $k \ll N$, which mixes extremely fast)
• The two components are connected by a single edge between a cycle node $x$ and a clique node $y$.

The lazy random walk on $G$ has a mixing time dominated by the cycle's slow exploration—though the clique gives the walker a way to "escape" the cycle temporarily. Now, add an edge between $x$ and another node in the clique $K$. Suddenly, the walker is much more likely to jump from $x$ into the clique and stick there (since the clique is dense, the walker will bounce around inside it for many steps) instead of continuing to traverse the cycle. As a result, the walker takes far longer to explore the entire cycle, increasing the overall mixing time of the graph.

This works because adding the edge reduces the spectral gap (the key eigenvalue metric tied to mixing time)—a smaller spectral gap means slower mixing.

3. Key Rules for How Mixing Time Changes With Edge Additions #

When adding edges one by one, the mixing time doesn't always decrease monotonically. Here are some critical points to remember:

• Conductance vs. Spectral Gap: Mixing time depends on both conductance and the spectral gap of the transition matrix. Adding an edge can improve one but hurt the other in edge cases (like the counterexample above).
• Lazy vs. Non-Lazy Walks: Counterexamples are more common for lazy random walks (where the walker can stay in place with 50% probability). For non-lazy walks (where the walker must move every step), adversarial additions are harder to construct but still exist.
• Guaranteed Monotonicity: There are scenarios where adding edges always reduces mixing time. For example:
  • Adding edges that increase the graph's minimum degree.
  • Adding edges to a tree (since trees have no cycles, any edge creates a shortcut that speeds up the walker).

4. Resources to Deepen Your Understanding #

If you want to formalize this knowledge, here are some go-to resources:

• Textbooks:
  • Markov Chains and Mixing Times by Levin, Peres, and Wilmer: The definitive guide to mixing time, with detailed sections on graph structure and edge effects.
  • Spectral Graph Theory by Fan Chung: Explains the tight link between eigenvalues, conductance, and mixing time.
• Core Concepts: Focus on learning about spectral gaps, conductance, and lazy vs. non-lazy random walks—these are the foundations for understanding how edge additions affect mixing time.

内容的提问来源于stack exchange，提问作者learner