Statistics

Classical vs Path Coupling on a Geometric State Space: Glauber Dynamics for (q)-Colorings of (C_n)

Authors: Iz Tecum
Comments: 26 Pages.

We analyze one coupling of single-site Glauber dynamics for proper (q)-colorings of the cycle (C_n) in two ways.Drift on the Hamming disagreement count and path coupling on Hamming-adjacent pairs give the one-step contractions[mathbb{E}bigl[d_{H}(X_1,Y_1)bigr]lealpha_{mathrm{cl}}(q,n),d_{H}(X_0,Y_0),qquadmathbb{E}bigl[d_{G}(X_1,Y_1)bigr]lealpha_{mathrm{pc}}(q,n),d_{G}(X_0,Y_0),]with (alpha_{mathrm{cl}}(q,n)=1-(q-4)/bigl(n(q-2)bigr)) and (alpha_{mathrm{pc}}(q,n)=1-(q-6)/bigl(n(q-2)bigr)), both attained. The thresholds are(qge5) and (qge7), and the constants separate by (2/bigl(n(q-2)bigr)) uniformly in (n). The gap is geometric.Transposing two colors across an edge produces a pair at Hamming distance (2) that no single recoloring connects,so the path metric (d_{G}) of the color graph charges a created disagreement (+2) rather than (+1); such pairspack (lfloor n/2floor) to a cycle, giving (operatorname{diam} d_{H}=n) and (operatorname{diam} d_{G}=lfloor3n/2floor) for(qge5), hence closed (O(nlog n)) bounds for both methods. The loss is attributable to the sparse edge setrather than to path coupling, since the complete edge set recovers (alpha_{mathrm{cl}}). Exact enumeration on (C_4)confirms every bound and gives worst-start (t_{mathrm{mix}}(0.05)=57,29,22,19,18) for (q=3,dots,7).
Category: Statistics