MathLabs

微分方程与动力系统

遍历理论

研究动力系统长期平均行为的学科,并将其与保测变换联系起来。

直观如果一直以同一个古怪的角度旋转下去,最终会走遍每个地方吗?

在一个圆形刻度盘上标记一点,反复将它旋转一个固定角度,该角度是整圈的一个无理数分数——比如约 137.5∘137.5^\circ 的黄金角,向日葵种子和松果鳞片正是按这个角度生长的。由于角度是无理数,这个点永远不会精确回到起点,而令人惊讶的是,它最终会任意接近圆上的每一个点,以与弧长成比例的频率经过每一段小弧。这里没有任何随机性——规则只是同一个刚性旋转不断重复——但长期统计看起来完全就像这个点是均匀随机选取的一样。这种均匀分布现象,以及确定性规则在无限时间内产生哪些平均性质这一问题,正是遍历理论的研究主题。

交互式单位圆,展示一个点按无理数黄金角反复旋转,说明均匀分布现象。
反复将theta滑块拖到黄金角 137.5∘137.5^\circ:被标记的点永远不会精确重复,但经过足够多圈后,它扫出了一个在圆上均匀分布的稠密点集——这正是无理数旋转 T(x)=x+α(mod1)T(x)=x+\alpha \pmod 1 的均匀分布性与遍历性背后的几何图景。

大学保测变换

定义: 保测变换

设 (X,F,μ)(X,\mathcal F,\mu) 为一个概率空间(集合 XX、可测子集的 σ\sigma-代数 F\mathcal F,以及满足 μ(X)=1\mu(X)=1 的测度 μ\mu)。映射 T:X→XT:X\to X 称为保测的,若对任意 A∈FA\in\mathcal F 都有 μ(T−1A)=μ(A)\mu(T^{-1}A) = \mu(A)——即将落入 AA 的点构成的集合的测度,等于 AA 本身的测度。直观地说:施加 TT 既不产生也不消灭概率质量,只是重新安排其所在位置。

μ(T−1A)=μ(A)∀ A∈F\mu(T^{-1}A) = \mu(A) \quad \forall\, A \in \mathcal{F}

有三个例子支撑着这一理论。圆 [0,1)[0,1) 上、α\alpha 为无理数的无理数旋转 T(x)=x+α(mod1)T(x)=x+\alpha \pmod 1 保持通常的(勒贝格)长度,因为旋转一段弧不会改变其长度。倍增映射 T(x)=2x mod 1T(x)=2x\bmod 1 同样保持勒贝格测度——它恰好是二对一的,一个区间的两个原像分支各自被压缩了 22 倍,因此它们的总长度恰好还原出原来的长度。而伯努利移位(独立抛硬币,每次移动一步)保持无限抛硬币序列空间上自然的乘积概率测度,因为把一列独立的抛掷移动一步,得到的仍是独立同分布的抛掷。

T−1A=A  ⟹  μ(A)∈{0,1}T^{-1}A=A \;\Longrightarrow\; \mu(A)\in\{0,1\}

保测变换 TT 称为遍历的,若每个 TT-不变集合本质上都是平凡的:对任意可测集 AA 都有 T−1A=A  ⟹  μ(A)∈{0,1}T^{-1}A=A \;\Longrightarrow\; \mu(A)\in\{0,1\}。等价地说,系统不能被拆分成两个正测度的部分,使得 TT 永远不将它们混合在一起——不存在对动力学进行非平凡分解的方式。无理数旋转与倍增映射相对于勒贝格测度都是遍历的,但原因完全不同,下表将精确说明这一点。

三个典型例子的遍历性与混合性
变换是否遍历是否混合
无理数旋转 T(x)=x+α(mod1)T(x)=x+\alpha \pmod 1是——每条轨道都均匀分布否——刚性旋转永远不会把两段弧混合在一起
倍增映射 T(x)=2x mod 1T(x)=2x\bmod 1是是——相隔很远的时刻之间的相关性会衰减为零
恒等映射 T(x)=xT(x)=x否(除非 XX 只有一个点)——每个集合都是不变的否

大学伯克霍夫遍历定理与庞加莱回归定理

设 TT 是概率空间 (X,F,μ)(X,\mathcal F,\mu) 上的保测变换,f∈L1(μ)f\in L^1(\mu)。则时间平均 Snf(x)n\frac{S_nf(x)}{n} 对 μ\mu-几乎每个 xx 都收敛于一个 TT-不变的极限 fˉ(x)\bar f(x),且满足 ∫Xfˉ dμ=∫Xf dμ\int_X \bar f\,d\mu = \int_X f\,d\mu。此外若 TT 是遍历的,则 fˉ(x)=∫Xf dμ a.e.\bar f(x)=\int_X f\,d\mu\ \text{a.e.}——沿单条轨道的时间平均等于空间平均。

为什么成立?

这正是物理学家几十年来在没有证明的情况下使用的直觉(统计力学中玻尔兹曼的遍历假设)的严格版本:要计算某个量的长期平均,你既可以让一个系统演化很长时间并观察它,也可以在某一瞬间对整个系统系综求平均——而对遍历系统而言,这两种听起来截然不同的计算给出完全相同的答案。

证明

第一步(不变的上极限与下极限)。定义 f∗(x)=lim sup⁡n→∞Snf(x)nf^*(x)=\limsup_{n\to\infty}\frac{S_nf(x)}{n} 与 f∗(x)=lim inf⁡n→∞Snf(x)nf_*(x)=\liminf_{n\to\infty}\frac{S_nf(x)}{n}。由于 Sn+1f(x)=f(x)+Snf(Tx)S_{n+1}f(x) = f(x) + S_nf(Tx),两边除以 n+1n+1 并令 n→∞n\to\infty,可得 f∗(Tx)=f∗(x)f^*(Tx)=f^*(x) 及 f∗(Tx)=f∗(x)f_*(Tx)=f_*(x):两者都是 TT-不变函数。

第二步(极大遍历定理)。对 λ∈R\lambda\in\mathbb R,令 Aλ={x:sup⁡nSnf(x)/n>λ}A_\lambda=\{x: \sup_n S_nf(x)/n>\lambda\} 为时间平均的部分和曾经超过 λ\lambda 的点的集合。关键的技术引理(通过考虑 g=f−λg=f-\lambda 及部分和的最大值 Mn(x)=max⁡(0,S1g(x),…,Sng(x))M_n(x)=\max(0,S_1g(x),\dots,S_ng(x)),再逐项利用 Mn(Tx)≥Skg(Tx)M_n(Tx)\ge S_kg(Tx) 并在 Mn>0M_n>0 的集合上积分来证明)给出 ∫Aλf dμ≥λ μ(Aλ)\int_{A_\lambda} f\,d\mu \ge \lambda\,\mu(A_\lambda)。

第三步(把 f 与 f_ 夹逼到一起)。反证:假设 f∗>f∗f^*>f_* 在一个正测度集合上成立;则存在有理数 α<β\alpha<\beta,使得 E={x:f∗(x)<α<β<f∗(x)}E=\{x: f_*(x)<\alpha<\beta<f^*(x)\} 具有正测度。由于 f∗,f∗f^*,f_* 不变,EE 是 TT-不变的,因此可以只考虑 EE 上的情形。对 EE 上的 f−βf-\beta 应用极大不等式,迫使 ∫Ef dμ≥βμ(E)\int_E f\,d\mu\ge\beta\mu(E);类似地对 α−f\alpha-f 应用,迫使 ∫Ef dμ≤αμ(E)\int_E f\,d\mu\le\alpha\mu(E);由于 α<β\alpha<\beta 且 μ(E)>0\mu(E)>0,两者矛盾。因此 f∗=f∗f^*=f_* 几乎处处成立,极限 fˉ(x)=lim⁡nSnf(x)/n\bar f(x)=\lim_n S_nf(x)/n 几乎处处存在且 TT-不变。

第四步(积分匹配,以及遍历情形)。一个控制收敛论证(截断 ff 并再次利用极大不等式控制尾部)可证明 ∫Xfˉ dμ=∫Xf dμ\int_X \bar f\,d\mu = \int_X f\,d\mu。最后,若 TT 是遍历的,则 TT-不变函数 fˉ\bar f 必须几乎处处为常数(这正是遍历性的定义应用于其水平集 {fˉ≤c}\{\bar f\le c\} 的结果,每个这样的水平集都是 TT-不变的,因而测度为 00 或 11);结合积分相等,该常数必为 ∫Xf dμ\int_X f\,d\mu,由此得到 fˉ(x)=∫Xf dμ a.e.\bar f(x)=\int_X f\,d\mu\ \text{a.e.}。

设 TT 是概率空间(更一般地,有限测度空间)(X,F,μ)(X,\mathcal F,\mu) 上的保测变换,A∈FA\in\mathcal F 满足 μ(A)>0\mu(A)>0。则 AA 中几乎每个点都会无穷多次回到 AA:对几乎每个 x∈Ax\in A,存在无穷多个 n≥1n\ge1 使得 Tnx∈AT^nx\in A。

为什么成立?

如果空间是有限的,并且什么都不会被消灭(保测性),那么一个区域就不可能永远把点不断送往全新的、从未到访过的领域——最终系统必须开始重新造访已经去过的地方,原因很简单:已经没有新的地方可以安放返回的测度了。

证明

第一步(永不返回的点)。令 A0={x∈A:Tnx∉A ∀n≥1}A_0=\{x\in A: T^nx\notin A\ \forall n\ge1\} 为 AA 中永不返回 AA 的点。集合 A0,T−1A0,T−2A0,…A_0, T^{-1}A_0, T^{-2}A_0,\dots 两两不相交:若 x∈T−iA0∩T−jA0x\in T^{-i}A_0\cap T^{-j}A_0 且 i<ji<j,则 Tix∈A0T^ix\in A_0,但同时对 j−i≥1j-i\ge1 有 Tjx=Tj−i(Tix)∈AT^j x = T^{j-i}(T^ix) \in A,这与 Tix∈A0T^ix\in A_0 永不返回 AA 矛盾。因此 T−iA0∩T−jA0=∅ (i≠j)T^{-i}A_0 \cap T^{-j}A_0=\varnothing\ (i\ne j)。

第二步(永不返回集的测度为零)。由于 TT 保测,对任意 ii 都有 μ(A0)=μ(T−iA0)\mu(A_0)=\mu(T^{-i}A_0)。若 μ(A0)>0\mu(A_0)>0,则可数个两两不交的集合 T−iA0T^{-i}A_0(i=0,1,2,…i=0,1,2,\dots)都具有相同的正测度,其并集测度将为无穷大——但这与 μ(X)<∞\mu(X)<\infty(实际上 μ(X)=1\mu(X)=1)矛盾。因此 μ(A0)=0\mu(A_0)=0。

第三步(只有限次返回的点集测度也为零)。令 B={x∈A:x returns to A only finitely often}B=\{x\in A: x\ \text{returns to}\ A\ \text{only finitely often}\}。将 BB 写成对 kk 的可数并,本质上是移位动力学下 TkAT^kA 的永不返回集,即 B=⋃k≥0T−k{x∈TkA:x never returns to TkA}B=\bigcup_{k\ge0} T^{-k}\{x\in T^kA: x\ \text{never returns to}\ T^kA\},每一项都可以将第一、二步的论证应用于 TkAT^kA(代替 AA,并用 μ(TkA)=μ(A)\mu(T^kA)=\mu(A))而得到测度为零。由可数次可加性,μ(B)=0\mu(B)=0。

第四步(结论)。由于 μ(B)=0\mu(B)=0,每个 x∈A∖Bx\in A\setminus B(在 AA 中具有满测度)都按 BB 的定义无穷多次返回 AA。这正是定理的结论。

进阶混合:比遍历性更强的性质

定义: 强混合

保测变换 TT 称为(强)混合的,若对所有可测集 A,BA,B 都有 lim⁡n→∞μ(T−nA∩B)=μ(A)μ(B)\lim_{n\to\infty}\mu(T^{-n}A\cap B)=\mu(A)\mu(B):nn 步之后落回 AA 的 BB 的比例,收敛到 AA 与 BB 统计独立时应有的值。混合蕴含遍历性(取 B=AB=A 且 T−1A=AT^{-1}A=A:此时 μ(A)=μ(A∩A)→μ(A)2\mu(A)=\mu(A\cap A)\to\mu(A)^2,迫使 μ(A)∈{0,1}\mu(A)\in\{0,1\}),但反之不成立。

无理数旋转为何是遍历的却不是混合的?取 A=BA=B 为一段小弧:将其旋转 nαn\alpha 只是把同一段小弧刚性地移动到圆上别处,因此 T−nA∩AT^{-n}A\cap A 要么为空,要么(由于旋转均匀分布,对无穷多个 nn)再次与 AA 的几乎全部非常接近——重叠比例从不趋于独立情形下的值 μ(A)2\mu(A)^2,而是不断振荡回到接近 μ(A)\mu(A) 的水平。相比之下,倍增映射会以指数速度将每一个小区间在整个空间中拉伸并折叠,真正地将其搅混——这正是其混合性的机制,并最终使得像 r=4r=4 的逻辑斯蒂动力学这样的混沌映射,在统计意义上可以被当作"和随机一样好"来处理。

大学实际应用与典型例题

遍历理论把"无限时间上的平均行为"变成一个可计算、可证明的命题,这正是统计力学用单一物理系统的长期平均代替系综平均(玻尔兹曼的遍历假设)所需要的;正是数据压缩用来定义熵率、从而限定一个信源可压缩程度(通过相应移位的科尔莫戈罗夫-辛熵)所需要的;正是像谷歌PageRank这样的搜索引擎,用来保证随机网页浏览者具有唯一长期访问频率(马尔可夫链的不变测度)所需要的;也正是由混沌映射构建的密码学伪随机数生成器,用来证明其输出可被视为统计随机所需要的。在每一种情形下,遍历性与混合性正是允许把单条确定性轨道当作携带了整个系统统计信息来对待的依据。

例题: 无理数旋转访问给定弧的频率是多少?

设 T(x)=x+α(mod1)T(x)=x+\alpha\pmod 1(α\alpha 为无理数)作用在带勒贝格测度的圆 [0,1)[0,1) 上,并设 A=[0,0.3)A=[0,0.3)。对一个典型起点 x0x_0,当 n→∞n\to\infty 时,前 nn 次迭代 x0,x1,…,xn−1x_0,x_1,\dots,x_{n-1} 落入 AA 的比例是多少?

解答

这正是取 f=1Af=\mathbf 1_A(即 AA 的指示函数)的伯克霍夫遍历定理计算:时间平均 1n∑k=0n−11A(xk)\frac1n\sum_{k=0}^{n-1}\mathbf 1_A(x_k) 恰好就是前 nn 次迭代落入 AA 的比例。

无理数旋转是关于勒贝格测度的遍历变换的经典例子(这实质上就是外尔均匀分布定理:任何 TT-不变集合展开为傅里叶级数后,由于旋转会把各项乘以 e2πikα≠1e^{2\pi i k\alpha}\ne1,所有非零傅里叶系数都必须消失,只剩下常数函数)。

由于 TT 是遍历的,伯克霍夫定理以最强的形式成立:对每一个典型起点(而不仅仅是对起点求平均),时间平均都等于空间平均。空间平均为 ∫X1A dμ=μ(A)=0.3−0=0.3\int_X \mathbf 1_A\,d\mu = \mu(A) = 0.3-0 = 0.3。

因此,轨道停留在 AA 中的长期时间比例恰好是 0.30.3,无论从哪个 x0x_0 出发(除去一个测度为零的例外集合)——这正是"确定性旋转在统计上的表现,与每次在 AA 中均匀随机取点完全一样"这一说法的严格版本。

例题: 有偏数据源能被压缩到什么程度?伯努利移位的科尔莫戈罗夫-辛熵

某数据源发出独立比特,每个比特以概率 p=0.3p=0.3 取 11,以概率 0.70.7 取 00——这可以遍历地建模为具有乘积测度 (0.3,0.7)(0.3,0.7) 的序列空间上的伯努利移位。计算其熵率(该移位的科尔莫戈罗夫-辛熵,这里等于单个符号的香农熵),根据香农信源编码定理,这就是无损压缩该信源平均每个符号所需的最少比特数。

解答

对于独立同分布(伯努利)信源,移位映射的科尔莫戈罗夫-辛熵化简为单个符号的普通香农熵:h=−∑ipilog⁡2pih=-\sum_i p_i\log_2 p_i。

代入 p1=0.3p_1=0.3,p0=0.7p_0=0.7:h=−0.3log⁡20.3−0.7log⁡20.7h=-0.3\log_2 0.3-0.7\log_2 0.7。

分别计算各项:−0.3log⁡20.3=0.3×1.737=0.521-0.3\log_2 0.3 = 0.3\times1.737=0.521 比特,−0.7log⁡20.7=0.7×0.515=0.361-0.7\log_2 0.7=0.7\times0.515=0.361 比特(用 log⁡20.3≈−1.737\log_2 0.3\approx-1.737,log⁡20.7≈−0.515\log_2 0.7\approx-0.515)。

相加得 h≈0.881 bitsh\approx0.881\ \text{bits}。因此平均而言,任何无损编码都无法将该信源压缩到每个符号约 0.8810.881 比特以下(明显低于公平硬币所需的每符号 11 比特,这正是因为偏置使信源更可预测,从而更可压缩)——而香农定理保证这一界限是可以达到的。

变换 T:X→XT:X\to X 保持概率测度 μ\mu,即 μ(T−1A)=μ(A)\mu(T^{-1}A) = \mu(A)。这个等式必须对哪些集合 AA 成立?

根据伯克霍夫遍历定理,对于遍历的无理数旋转 T(x)=x+α(mod1)T(x)=x+\alpha \pmod 1 及 A=[0,0.3)A=[0,0.3),典型轨道停留在 AA 中的长期时间比例是多少?

根据庞加莱回归定理,对于有限测度空间上满足 μ(A)>0\mu(A)>0 的保测系统,AA 中几乎每个点……

某信源发出独立同分布比特,P(1)=0.3P(1)=0.3。其熵率(对应伯努利移位的科尔莫戈罗夫-辛熵),以比特为单位保留两位小数,最接近:

参考文献

  1. Peter Walters (1982). An Introduction to Ergodic Theory
  2. George D. Birkhoff (1931). Proof of the Ergodic Theorem
  3. John von Neumann (1932). Proof of the Quasi-Ergodic Hypothesis
  4. Hillel Furstenberg (1981). Recurrence in Ergodic Theory and Combinatorial Number Theory