路径耦合

局部距离怎样沿路径连接 ​

设两个状态的最短路径为$x=x_0,x_1,\dots ,x_m=y$。假如相邻转移分布之间各有一份便宜的搬运方案，它们可以通过共同中间边缘粘起来。三角不等式保证端到端的平均搬运成本不超过分段成本之和。

这种粘合不要求所有局部耦合预先由同一个随机数实现。也不要求沿辅助路径真实运行原链：路径只是证明中比较不同初态的工具，原链仍只走一步。

有限粘合的具体证明 ​

给三份分布$\mu ,\nu ,\eta$，令$A(x,y)$耦合$\mu ,\nu$，$B(y,z)$耦合$\nu ,\eta$。定义

当$\nu (y)=0$，非负性保证两张表在该中间点的整列或整行都为零，所以置零不会损失质量。分别求和可验$R$的$(x,y)$、$(y,z)$边缘正是$A,B$。再由$d(x,z)\le d(x,y)+d(y,z)$得到$W_d$的三角不等式。

有限概率表的可行集合闭且有界、目标连续，所以最优耦合存在。对前述最短路径使用三角不等式及式(1)，

取$\mu ,\nu$的最优耦合$Q$，对每对$(x,y)$选一份实现式(5)的转移耦合$Q_{xy}^{\prime }$，并混合成$\sum _{x,y}Q(x,y)Q_{xy}^{\prime }$。它的两个边缘是$\mu P,\nu P$，平均成本不超过$\rho \sum Q(x,y)d(x,y)$，这就证明式(2)。有限集合中的逐对选择没有可测选择问题。

从平均距离到事件误差 ​

对任意耦合，$\mathbf{1}\{X\ne Y\}\le d(X,Y)/\delta$。实际使用耦合不等式理路耦合法Coupling method · Probability coupling在共同概率空间中构造具有指定边缘的随机变量，并用它们相遇的概率比较分布。，得到

有限Markov链至少有一份平稳分布理路平稳分布Stationary distribution经马尔可夫转移后保持不变的状态分布。：例如取任意初始分布的Cesàro平均${\overline{\mu }}_N=N^{-1}\sum _{j=0}^{N-1}\mu P^j$，在有限概率单纯形中选收敛子列；${\overline{\mu }}_{N}P-{\overline{\mu }}_N=(\mu P^N-\mu )/N\to 0$，其极限便不变。

若$\pi ,\tilde{\pi }$都平稳，式(2)给$W_d(\pi ,\tilde{\pi })\le \rho W_d(\pi ,\tilde{\pi })$，故二者相等。再迭代式(2)，用$W_d({\delta }_x,\pi )\le D$与式(6)，便得到式(3)。这份证明不需要先假定链不可约，平稳质量可以集中在一个真子集上。

逐坐标刷新独立比特 ​

在$\mathrm{\Omega }=\{0,1{\}}^n$上，每轮均匀选坐标$i$，将其重新抽成Bernoulli$(p_i)$，其余坐标不变；允许$p_i=0$或1。目标是这$n$个Bernoulli分布的乘积。

辅助图连接只差一个坐标的状态，边长1，路径距离就是Hamming距离。若初态只在$j$不同，让两条链选同一坐标、用同一均匀数重抽。选到$j$时差异消失，选其他坐标时原差异保留且不会新添差异。所以

$n=3$时，认证TV不超过$1/20$需要检查$3(2/3{)}^t\le 1/20$。第10步的这份上界仍大于$1/20$，第11步已小于，所以式(4)给11次单坐标更新。它是证书给出的足够步数，不是已证明的真实最小混合时间。

若某个$p_i$退化为零，乘积目标可以只在真子集有质量，链也可以不可约性失败；上述耦合证明仍然成立，因为不合目标的坐标最终被刷新。这是“不必额外要求不可约”的具体例子。

非均匀扫描与缺失坐标 ​

改为以固定$q_i>0$选坐标，对只在$j$不同的初态，一步期望距离为$1-q_j$。因此可以取$\rho =1-\underset{i}{min}{q}_i$。给不同坐标赋正权重$w_i$时，该对的距离与期望都乘$w_j$；对这个独立刷新模型，单纯换权不能消除最慢坐标的瓶颈。

若某个$q_j=0$，该坐标永不刷新，两份只在$j$不同的初态永久保留差异，严格收缩失败。不能把未更新坐标从距离中设成零而继续声称控制完整状态的TV；那样得到的不是本页所要求的度量。

哪些局部检查不够 ​

辅助图若不连通，只在各分量内部验证式(1)，不能比较不同分量。最极端的例子是两点、无辅助边、恒等转移：所有边条件真空成立，却有两份不同的平稳点质量。

若使用平方Hamming数而非路径距离，三角不等式可能失败；两段各差一位时成本为1+1，端点差两位却为4，粘合证明无法成立。若边耦合的一侧偷偷使用另一转移核，即使距离迅速缩小，也不能支持原$P$的结论。

当得到的只是$\rho =1$，式(2)至多说明不扩张，没有式(4)的有限几何预算。这不证明原链不混合；可能需要其他距离、多步耦合或其他分析。严格小于一的量词不能由数值上“接近一”替代。

有限证书如何审计 ​

若显式给$N=|\mathrm{\Omega }|$个状态、$M$条辅助边和每边一张$N\times N$联合转移表，可逐行逐列核对边缘、非负性、归一化，再计算式(1)的成本。已有全部距离时，这部分需$O(M{N}^2)$算术操作。

若距离尚未给出，可先用全点对最短路计算，稠密实现为$O(N^3)$时间、$O(N^2)$空间。逐边表可以流式读取，工作空间不必同时保存$M$张表；精确有理输入的位成本还取决于分母增长。这些显式成本可能仍然很大，实际收益来自利用模型对称性或局部依赖，统一证明很多边的同一种耦合公式。

通过的证书应报告转移核、辅助图、边长、$\rho ,\delta ,D$及目标精度。某条边失败只能说明这一份局部证书没有通过，不能据此断言没有别的耦合能收缩。

与局部条件模型的接口 ​

有限Ising模型理路有限 Ising 模型Finite Ising model · Ising model · 伊辛模型 · 有限自旋系统在有限图上给二值自旋的相邻相互作用和外场赋概率，推导局部条件更新，并由树与回路的边变量区分联合依赖。的一次热浴更新可能消灭旧差异，也可能让相邻自旋新生差异。逐项支付这些变化才是式(1)的内容，不能因为每次只更新一位就认为Hamming距离只会下降。

Dobrushin影响矩阵理路Dobrushin 收缩条件Dobrushin contraction condition · Dobrushin influence matrix · Dobrushin interdependence matrix · 多布鲁申影响矩阵用一个坐标变化对其他全条件的最大影响构造误配递推，认证有限Gibbs扫描的边缘误差与加权收缩。可把新生误配写成条件概率变化的预算。对加权Hamming距离，改变第$j$个输入坐标会向各接收坐标$i$传播，因此使用含扫描概率和距离权重的列和；按坐标误配向量递推时则使用接收行。这是同一个影响矩阵的两种计算接口，需要保持下标方向。