P-stability · why the switch chain mixes fast

Steps 0Edges changed 0 / 0

The switch move keeps every degree fixed

Left: a bipartite network — rows connected to columns. Right: the same network as an adjacency matrix. The degree sequence is the row and column sums in the margins.

A switch picks two edges (i,a) and (j,b) whose crossed pairs are absent, and swaps endpoints. Two cells go dark, two light up, and every margin stays exactly the same.

Hinge flips and the switch

A switch is really two hinge flips in a row. One hinge flip moves a single edge endpoint, (i,a) → (i,b): column a loses a degree, column b gains one, and the network briefly has a neighbouring degree sequence $d'$ at L1-distance 2 from $d$. The second flip moves it back. P-stability is a statement about exactly these neighbouring sequences: $\Omega(d')$ is never much larger than $\Omega(d)$, so a chain that wanders through them spends most of its time in $\Omega(d)$ itself — which is how the guarantee transfers to the switch chain.

Every network reachable this way is a realization of the same degree sequence. Their set, $\Omega(d)$, is finite but astronomically large. The starting network is one point in it.

addedremovedmargin off by onepresent

P-stability: a state space without bottlenecks

Think of $\Omega(d)$ as a state space where every state is one whole network — a complete realization of $d$ — and a switch is one step from a realization to a neighbouring one. Then a random walk composed of these steps mixes fast when the state space is well-connected and slowly when there are bottlenecks.

How P-stability rules out bottlenecks

How do you prove there are no bottlenecks? With a canonical-path argument: pick one route (a sequence of switches) between every pair of states, then check that no single state is crossed by too many routes (the congestion $\rho$) and that no route is too long ($\ell$). If routes are spread evenly, the state space has no narrow passage, and a random walk cannot get stuck. Those two numbers bound the mixing time:

$$T(\epsilon) \le \rho(f)\,\ell(f)\,\ln\!\left(\frac{|\Omega(d)|}{\epsilon}\right)$$ρ(f) flow congestion · ℓ(f) longest canonical path · T(ε) steps to within ε of uniform

Where P-stability comes in. Bounding the congestion means counting the routes that cross a given state $Z$. The standard trick: any route crossing $Z$ can be reconstructed from $Z$ plus a "leftover" network. That leftover is not a realization of $d$ — it is a realization of a slightly perturbed sequence $d'$, off by one or two degrees, which is exactly what a hinge flip produces. So the number of routes through $Z$ is at most $\mathrm{poly}(n)\cdot|\Omega(d')|$. P-stability caps that count:

$$|\Omega(d')| \le p(n)\cdot|\Omega(d)|$$

No state carries more than a polynomial multiple of its fair share of routes, so the congestion is polynomial, so the switch chain has no bottleneck and mixes in polynomially many steps.

The counting argument in detail

A canonical path from $X$ to $Y$ is a fixed sequence of switches, so every intermediate state is itself a realization in $\Omega(d)$. The walk never leaves $\Omega(d)$.
Congestion counts paths through a state $Z$. An encoding argument reconstructs any such path from $Z$ plus one "leftover" network $\eta = X \oplus Y \oplus Z$ (the symmetric difference of the three edge sets), plus $O(n^2)$ bits of bookkeeping. Because $Z$ sits partway along the route, $\eta$ is not in $\Omega(d)$: its degrees are off by one or two at a handful of vertices, so $\eta\in\Omega(d'')$ for some $d''$ at L1-distance $\le 2$ from $d$. Hence $\#\text{paths through }Z \le \mathrm{poly}(n)\,|\Omega(d'')|$.
Without P-stability, $|\Omega(d'')|$ could be exponentially larger than $|\Omega(d)|$. P-stability gives $|\Omega(d'')| \le p(n)\,|\Omega(d)|$; since each state carries weight $\sim 1/|\Omega(d)|$, the congestion is $\rho \le \mathrm{poly}(n)\,p(n)$.
Path length is polynomial for free: $\ell \le$ number of edges on which $X$ and $Y$ differ $= O(n^2)$.
$\ln|\Omega(d)| \le O(n^2)$ since there are at most $2^{n^2}$ matrices. Multiply: $T(\epsilon)$ is polynomial in $n$; the large exponent is the product of the polynomials above.

The perturbed sequences $d''$ appear only in the encodings used to count routes — never as states of the chain.

300 walkers start at the same realization in both state spaces. Watch how far each population is from uniform.

Step 0Distance to uniform 1.00 · 1.00

Steps per chain T 8N 0z —p —

Too few steps and the test quietly lies

Run N independent chains from the observed network, each for T steps, and measure a statistic on every sample — here community structure: the share of edges that fall inside the two known groups (a simple modularity). Together the sampled values form the null distribution.

With a small T the samples are still close relatives of the starting network: the histogram hugs the observed value and z collapses toward 0 — the test says "nothing unusual" whether or not something is. Nothing in the p-value reveals this.

With T at the proven mixing bound, samples are approximately uniform draws from Ω(d) and the comparison means what it claims:

$$z = \frac{f(G_{\text{obs}}) - \bar f}{s_f}$$$$p = \frac{\#\{i : f(M_i) \ge f(G_{\text{obs}})\} + 1}{N + 1}$$

null samplesobserved

Practical caveats

The bound is loose

Canonical-path polynomials carry large exponents ($O(n^{13})$ for general degree sequences, where $n$ is the number of vertices). In practice P-stability is used qualitatively: it certifies the true mixing time is polynomial, which justifies trusting a cheap empirical stopping rule.

Check the null's shape

A z-score assumes the null histogram is roughly bell-shaped. Some statistics aren't — algebraic connectivity is exactly 0 for any disconnected sample, so the histogram gets a spike at 0 next to a separate hump. Look at the histogram first; if it isn't bell-shaped, use the rank p-value, which only counts samples at least as extreme as the observed and works for any shape.

N sets the floor