从过去耦合

为什么要固定终点 ​

一旦$H_T$是常值映射，补入更早的记录得到$H_{T^{\prime }}=H_T\circ F_{-T-1}\circ \cdots \circ F_{-T^{\prime }}$，输出仍是原来的常值。因此向过去扩展只会消除未知初态，已经确定的时刻0不会被改变。

向未来运行到首次相遇则不同：相遇时刻本身是随机选择的，某些状态容易成为合并入口，另一些状态只能在合并以后到达。把第一次相遇的位置当作平稳样本，可能偏向前者。重抽旧后缀也会破坏上述“已经确定的现在不会改变”的一致性。

精确输出的证明 ​

令$\tau =min\{T\ge 1:H_T\text{为常值}\}$。对每个确定的$m$，取$X\sim \pi$且独立于全部更新记录，令$Z_m=H_m(X)$。式(1)及不变性逐步给出$Z_m\sim \pi$；这里不要求实际程序会抽$X$，它只用于证明。

在$\{\tau \le m\}$上，$H_m$已是最终常值，所以$Z_m=Y$。由耦合不等式理路耦合法Coupling method · Probability coupling在共同概率空间中构造具有指定边缘的随机变量，并用它们相遇的概率比较分布。，

最后一步使用式(3)。因此输出律精确等于$\pi$，不是只在某个小误差范围内。若有另一份平稳分布，同一论证会迫使它也等于$\mathcal{L}(Y)$，所以全合并同时保证平稳律唯一。

一个可验证的停止条件 ​

若存在长度$L\ge 1$及$\gamma >0$，使$L$个独立更新映射的合成以至少$\gamma$的概率成为常值，则称它们提供一份同步块证书。把过去切成互不重叠的长度$L$块，任意一块先把全状态压成一点，之后的任何映射都不会重新分开。独立性给

期望界由整数尾和分组得到：每组$L$个尾概率均不超过相应的$(1-\gamma {)}^k$。所以这份局部证书既证明停止，也给粗成本界；不必把“链不可约非周期”误当成这份特定映射自动合并的理由。

铁磁热浴为什么只需两条轨迹 ​

若状态空间有偏序理路偏序Partial order · Partially ordered set满足自反、反对称和传递性的关系。，存在最小元$\mathrm{\perp }$和最大元$\mathrm{\top }$，且每个允许记录都使$\mathrm{\Phi }(\cdot ,U)$保序，则

只要两个极端终点相同，反对称性迫使全部终点相同；因此每轮只需回放两条轨迹。要求的是最小/最大元，不是随便选两个极小/极大元，也不是两条一般初态路径恰好相遇。

对有限铁磁Ising模型理路有限 Ising 模型Finite Ising model · Ising model · 伊辛模型 · 有限自旋系统在有限图上给二值自旋的相邻相互作用和外场赋概率，推导局部条件更新，并由树与回路的边变量区分联合依赖。，使用逐坐标次序$-1<+1$。局部场$a_i=h_i+\sum _j{J}_{ij}{\sigma }_j$随其他坐标递增，条件取正概率$p_i=1/(1+e^{-2a_i})$也递增。记录$U_t=(I_t,V_t)$，以固定正概率选$I_t$，用同一$V_t\sim \mathrm{Unif}(0,1)$在$V_t<p_{I_t}$时设为正。未更新坐标保持次序，更新坐标也不可能出现下轨迹为正、上轨迹为负。因此这份热浴实现理路Gibbs 采样器Gibbs sampler · Gibbs sampling轮流从目标联合分布的全条件分布抽取坐标，以条件更新组成保持联合目标不变的 Markov 核。保序。

有限参数还给${ϵ}_i=\underset{\sigma }{min}{p}_i(\sigma )>0$。连续$n$步恰按坐标$1,\dots ,n$更新，且每步$V<{ϵ}_i$，会把全部初态送到全正。若扫描概率为$q_i$，这个同步事件的概率是

这证明停止，但$\gamma$可能极小，不能把存在正概率当作高效性。式(7)其实不要求铁磁性；铁磁性用于式(6)的两条轨迹快捷检查。含负耦合时仍可验证全状态合并，只是两个极端未必夹住所有轨迹。

两自旋的短回放 ​

取一条正边、无外场、$e^{2J}=3$，两坐标均匀扫描。每个条件取正概率是$1/4$或$3/4$。指定已有记录

只回放$T=1$时，第二个自旋必成负，第一个仍未知；下、上终点分别为$--$和$+-$，不能输出。扩展至$T=2$，更早的记录先把第一个自旋强制为正，再重用原来的$U_{-1}$把第二个设为负，两条极端都到$+-$。

这份具体记录用于复算确定性回放，不声称某个精确实数随机数有正概率。相应的正概率同步事件是第一步选坐标1且$V<1/4$，第二步选坐标2且$V>3/4$，其概率为$1/64$。取$L=2$，式(5)给$E\tau \le 128$；它只是方便验证的粗上界。

更长历史中的同后缀核验 ​

三角形零外场、$e^{2J}=3$的八份记录，展示倍增时要保存什么。下图的每一列固定一份$(i,U)$，每次只补入左边缺少的旧列；$T=1,2,4$的两个极端像仍不同，$T=8$才相同。完整逐步回放见采样终点任务。图只核验这份记录的合并，不把条件于某个完成窗口的输出律当成平稳律。

同一链也可以选到永不合并的映射 ​

在$\{0,1\}$上，每轮以一半概率取恒等映射、一半概率取翻转映射。每个初态一步后都均匀，因此

已经一步混合。可是任意多个恒等或翻转的合成都仍是双射，从不把两个状态压成一点；式(3)失败。

若改为以一半概率取常零映射、一半概率取常一映射，单条轨迹仍有完全相同的$P$，却一步全合并。CFTP的成本依赖共同随机映射的构造，不能只看单链转移矩阵。

倍增成本与存储接口 ​

设最终尝试长度$T=2^k$，每次都从头回放。一个初态共执行$1+2+\cdots +T=2T-1$次映射求值；$T<2\tau$，因此跟踪$N=|\mathrm{\Omega }|$个初态时，求值次数小于$4N\tau$。结合式(5)，期望求值次数至多$4NL/\gamma$。单调快捷法只跟踪两个极端，把$N$替成2。

若每条随机记录可用固定大小对象保存，每个状态也按一个对象计，保留历史与当前全部图像需$O(T+N)$个对象；若显式保存每个随机映射的整张$N$项表，则历史存储变成$O(NT)$。自旋模型的两个状态本身需$O(n)$空间，历史再需$O(T)$条记录。每次热浴求值还要乘形成条件概率的实际成本，不能把复杂局部模型都算作常数时间。

时间筛选不是免费操作 ​

完整独立运行，每次使用独立随机源并等到完成，可得到独立平稳样本。但运行时间可能与输出值相关。只保留某个截止时间前完成的运行，或丢弃超时任务后把其余输出当成IID目标样本，通常会引入选择偏倚。有限资源下应保留未完成状态，并报告采用了什么筛选规则；单次已合并的历史证书不能证明经筛选样本集合的分布仍为$\pi$。

数学上的精确性还要求正确的随机接口和条件抽样。正有理概率可以用无偏随机位实现精确抽样；有限精度伪随机数、近似指数和错误的阈值舍入，不会因为外层叫CFTP就自动消失。公开的有理回放检查可以核验指定历史的合并，却不是对随机源真实性的检验。

与固定步数近似采样配合 ​

路径耦合理路路径耦合Path coupling · Bubley–Dyer path coupling · 邻点路径耦合在有限连通辅助图上只检验相邻初态的一步平均距离，再由耦合粘合与最短路把收缩推广到全部分布。与局部影响收缩理路Dobrushin 收缩条件Dobrushin contraction condition · Dobrushin influence matrix · Dobrushin interdependence matrix · 多布鲁申影响矩阵用一个坐标变化对其他全条件的最大影响构造误配递推，认证有限Gibbs扫描的边缘误差与加权收缩。给固定预算的TV误差；CFTP给随机运行长度下的精确平稳输出。前者可以在预算内返回带误差的近似结果，后者在尚未全合并时仍没有自己的精确结果。两种证书回答不同计算问题，可以共用一个正确的局部更新器，但不能互换停止规则。