变分距离

在 Markov 链的长时行为研究中，我们希望能够刻画两个分布之间的距离到底有多大。变分距离是其中一种方法。

阐述

设 $\mu,\nu$ 是 $\mathcal X$ 上的两个分布，定义它们之间的总变分距离为

$$d_{T V}(\mu, \nu)=\sup _{A \subseteq \mathcal{X}}|\mu(A)-\nu(A)|$$

这个距离并不容易计算，所以我们通常是给出一个它的上界或者下界的。

上界

耦合可以给出一个上界，因为

$$d_{T V}(\mu, \nu) \leq \inf \{\mathbb{P}(X \neq Y):(X, Y) \text { is a coupling of } \mu \text { and } \nu .\}$$

下界

当 $P$ 是一个有限状态空间、不可约、非周期性 Markov 链时，设 $A\subseteq\mathcal X$ 是一个无法从 $x$ 出发在 $i$ 步以内达到的集合，则我们有

$$d_{TV}(P^i(x,\cdot), \pi)\ge\pi(A)$$

实例

超立方体上的懒随机游走

考虑 $\mathcal X=\{0,1\}^n$，我们以 $1/2$ 的概率不动，$1/2$ 的概率随机选取一个坐标翻转。（也可以认为是随机选取一个坐标然后重设为随机值）。

• 用耦合的方法，可以得出对任意起始分布，都有

$$d_{TV}(\mu P^i,\pi)\le\mathbb P(X_i\ne Y_i)\le\mathbb P(T>i)$$

• 用下限的方法，可以得出在 $n/2$ 步以内，我们都有 $d_{TV}(P^i(0,\cdot),\pi)\ge 1-\pi(A_i)\ge 1/2$

性质

在离散变量情况下，它们具有如下性质：

1. 变分距离为 0，当且仅当它们全等；
2. 对称性
3. 三角不等式
4. 分布收敛等价于变分距离趋于 0
5. 一个更方便的计算公式：

$$d_{T V}(\mu, \nu)=\frac{1}{2} \sum_{x \in \mathcal{X}}|\mu(x)-\nu(x)|=\sum_{x: \mu(x)>\nu(x)} \mu(x)-\nu(x)$$

相关内容

参考文献