排序上鞅

单条路径可以偶尔向上走，甚至连续很多次上涨；证明不要求每次严格下降。要求的是在知道当前全部历史后，下一步的平均变化仍有统一负余量，且资本不能逃到负无穷。

这个余量给每一个未结束步骤标了至少 $\epsilon$ 的平均消耗。总可消耗量不超过初始势，因此平均未结束步数受到控制。

有偏随机游走的三倍界 ​

令 $x$ 为非负整数，在 $x>0$ 时以概率 $2/3$ 令 $x:=x-1$，以概率 $1/3$ 令 $x:=x+1$，到零停止。取 $V(x)=x$，有

因此 $\epsilon =1/3$，从 $x=4$ 出发，期望循环次数至多 $12$。向上走的分支并未被忽略；正是两种分支的加权平均给出了下降。

不靠不当交换极限的证明 ​

对条件不等式取期望并累加 $n$ 步，得到

非负性允许丢掉第一项，尾和等于 $\mathbb{E}min(T,n)$。再由单调收敛定理公理库单调收敛定理Monotone convergence theorem非负可测函数单调递增时，积分极限等于极限函数积分。令 $n\to \mathrm{\infty }$，即得运行时间界。这个证明只处理有界时刻的有限和，没有直接把一个可能无界的停时塞进可选停止定理。

普通非负上鞅还不够 ​

永不退出的循环可取 $V_n\equiv 1$，它是非负鞅，却不证明任何终止性质。缺失的是未终止时的严格平均进展。

若改为对称游走，从 $1$ 出发每次等概率增减，到零停止，$V(x)=x$ 的平均变化为零。该程序仍 AST，但期望时间无穷：在 $0,N$ 两端截停时，从 $1$ 出发的平均时间为 $N-1$，原终止时间不小于它，令 $N\to \mathrm{\infty }$ 即得无穷。它的 AST 可由先到 $N$ 而非零的概率为 $1/N$ 推出。因而不能给它找到满足本页有限初势、统一正下降条件的证书。

自动验证常从线性或多项式候选 $V$ 出发，把各分支的条件期望下降转成约束。还需检查可达状态上非负、表达式可积以及退出后的处理；只求出一个形式上的负漂移多项式不够。

更一般的 AST 规则允许下降幅度或下降概率依赖当前势值，从而覆盖没有有限期望时间的程序。[1] 本页只陈述最容易核算的统一加性版本，不能把它的充分条件当成 AST 的必要条件。