2026-09-15 · 卷积幂何时忘记起点

0. 导读与元结构 (Orientation & Meta-structure)

起点问题。 昨天已经知道：有限群上的卷积在 Fourier 侧变成逐块矩阵乘法。但这一代数恒等式何以成为概率论中的“混合”？若每一步都独立抽取群元素并左乘当前位置，则走了 $t$ 步后的分布是增量分布的 $t$ 次卷积；于是每个 Fourier 块都被提升到 $t$ 次幂。随机游走是否忘记起点，等价于所有非平凡表示块是否衰减。

对象与量词层。 固定有限群 $G$ 与概率测度 $\mu :G\to [0,1]$，满足 $\sum _{g\in G}\mu (g)=1$。令独立增量 $Y_1,Y_2,\dots$ 均服从 $\mu$，并从单位元出发定义

$$X_0=e,X_t=Y_t{Y}_{t-1}\cdots Y_1.$$

今天比较的对象是：每个时刻 $t\ge 0$ 的分布 ${\mu }^{\ast t}$；每个不可约酉表示 $\pi \in \hat{G}$ 的矩阵 $\hat{\mu }(\pi {)}^t$；以及 ${\mu }^{\ast t}$ 与均匀分布 $U$ 的总变差距离。结论中的量词是：对每个 $t$ 同时汇总全部非平凡不可约块，而不是只观察某个 eigenvalue（特征值）。

前置、机制与去向。 前置是有限群、矩阵范数、Cauchy--Schwarz inequality（Cauchy--Schwarz 不等式）及昨日的有限群 Plancherel 公式。主证明引擎只有三步：卷积幂变成矩阵幂；Plancherel 把偏离均匀的能量分配到非平凡块；总变差由 $L^2$ 能量控制。若增量测度在共轭下不变，Schur lemma（Schur 引理）还会把每个矩阵块压成一个 character ratio（特征标比）。去向是 Cayley 图谱隙、expander（扩张图）、洗牌的 cutoff phenomenon（截止现象）及群上的 Markov chain Monte Carlo。

弧线位置。 这是 exploration-2026-w38-noncommutative-fourier 的 Day 2/3：Day 1 建立静态 Fourier 块；今天让块随时间演化；Day 3 将比较表示维数、谱隙与 Cayley 图扩张。

1. 核心概念、定理与谱系 (Concept, Theorem & Lineage)

1.1 从群增量到概率卷积

对两个概率测度 $\mu ,\nu$ 定义概率卷积

$$(\mu \ast \nu )(x):=\sum _{y\in G}\mu (y)\nu (y^{-1}x).$$

它是独立随机变量 $YZ$ 的分布，其中 $Y\sim \mu$、$Z\sim \nu$。因而 $X_t$ 的分布是 ${\mu }^{\ast t}$，约定 ${\mu }^{\ast 0}={\delta }_e$。

有限群随机游走的三条基本结构事实是：

1. 均匀分布 $U(g)=|G{|}^{-1}$ 总是平稳，因为 $\mu \ast U=U$；
2. 游走不可约当且仅当 $\mathrm{supp}\mu$ 生成 $G$；
3. 若 $\mu (g)=\mu (g^{-1})$ 对所有 $g$ 成立，则游走关于 $U$ 可逆。

不可约性保证状态之间可达，却不单独保证 ${\mu }^{\ast t}\to U$；还需要排除周期振荡。最简便的充分条件是 laziness（惰性）：$\mu (e)>0$，配合不可约性便得到非周期性。

1.2 概率测度的 Fourier 块与时间演化

这里采用适合概率卷积的约定：对每个 $\pi \in \hat{G}$，定义

$$\hat{\mu }(\pi ):=\sum _{g\in G}\mu (g)\pi (g).$$

这与昨天对函数使用的归一化变换并不冲突：若 $f=|G|\mu$ 是相对于 $U$ 的密度，则

$$\frac{1}{|G|}\sum _{g}f(g)\pi (g)=\hat{\mu }(\pi ).$$

直接令 $x=yz$，可得

$$\widehat{\mu \ast \nu }(\pi )=\hat{\mu }(\pi )\hat{\nu }(\pi ),$$

从而对每个整数 $t\ge 0$，

$$\widehat{{\mu }^{\ast t}}(\pi )=\hat{\mu }(\pi {)}^t.$$

平凡表示块始终等于 $1$，它正编码总质量。其余块编码偏离均匀的全部信息。若 $\mu$ 对称，则

$$\hat{\mu }(\pi {)}^{\ast }=\sum _g\mu (g)\pi (g^{-1})=\hat{\mu }(\pi ),$$

故每个块是 Hermitian matrix（Hermitian 矩阵），可以用实特征值研究衰减；无对称性时则应关注算子范数或奇异值，而不能假装所有块都可正交对角化。

1.3 Plancherel 如何推出总变差混合上界

令 $N=|G|$、${\mu }_t={\mu }^{\ast t}$，并令

$$f_t(g):=N{\mu }_t(g)$$

为 ${\mu }_t$ 相对于 $U$ 的密度。总变差距离满足

$$\begin{array}{rl}\parallel {\mu }_t-U{\parallel }_{\mathrm{TV}}& :=\frac{1}{2}\sum _{g\in G}|{\mu }_t(g)-N^{-1}|\\ & =\frac{1}{2}{\mathbb{E}}_{g\sim U}|f_t(g)-1|\\ & \le \frac{1}{2}{({\mathbb{E}}_{g\sim U}|f_t(g)-1{|}^2)}^{1/2}.\end{array}$$

对 $f_t-1$ 应用有限群 Plancherel 公式：平凡表示块恰被减掉，而每个非平凡块为 $\hat{\mu }(\pi {)}^t$。于是得到 finite-group upper bound lemma（有限群上界引理）：对每个 $t\ge 0$，

$$\boxed{{\displaystyle \parallel {\mu }^{\ast t}-U{\parallel }_{\mathrm{TV}}^2\le \frac{1}{4}\sum _{\begin{array}{c}\pi \in \hat{G}\\ \pi \ne \mathbf{1}\end{array}}{d}_{\pi }\parallel \hat{\mu }(\pi {)}^t{\parallel }_{HS}^2.}}$$

这类由表示论控制群上随机游走的估计通常称为 Diaconis--Shahshahani upper-bound method。假设出现的位置很清楚：有限性使矩阵系数给出完整离散 Plancherel 分解；概率性固定平凡块；若要从上式读出几何衰减，还必须证明每个非平凡块的谱半径严格小于 $1$。

1.4 中心测度：矩阵频率退化为特征标比

若

$$\mu (xg{x}^{-1})=\mu (g)(\mathrm{\forall }x,g\in G),$$

则称 $\mu$ 为 central measure（中心测度、类测度）。对任意 $x\in G$，换元给出

$$\pi (x)\hat{\mu }(\pi )\pi (x{)}^{-1}=\hat{\mu }(\pi ).$$

不可约性与 Schur 引理迫使

$$\hat{\mu }(\pi )=a_{\pi }{I}_{V_{\pi }},a_{\pi }=\frac{1}{d_{\pi }}\sum _{g\in G}\mu (g){\chi }_{\pi }(g).$$

因此上界进一步化为

$$\boxed{{\displaystyle \parallel {\mu }^{\ast t}-U{\parallel }_{\mathrm{TV}}^2\le \frac{1}{4}\sum _{\pi \ne \mathbf{1}}{d}_{\pi }^2|a_{\pi }{|}^{2t}.}}$$

昨天说“只保留 character 不足以恢复一般函数”；今天并未反悔。恰恰因为中心测度是类函数，它的每个完整矩阵块才由 Schur 引理强制成为标量；特征标在这个受限子空间内恰好足够。

1.5 $S_3$ 的惰性换位游走

令 $T$ 是 $S_3$ 的三个换位组成的共轭类，并取

$$\mu =\frac{1}{2}{\delta }_e+\frac{1}{2}\mathrm{Unif}(T).$$

它对称、中心、支撑生成 $S_3$，且因 $\mu (e)>0$ 非周期。$S_3$ 的三个不可约表示为平凡表示、符号表示和二维标准表示；在换位类上的 character 值分别是 $1,-1,0$。所以

$$a_{\mathrm{triv}}=1,a_{\mathrm{sgn}}=0,a_{\mathrm{std}}=\frac{1}{2}.$$

上界引理立即给出

$$\parallel {\mu }^{\ast t}-U{\parallel }_{\mathrm{TV}}\le 2^{-t}.$$

在这个六状态例子中还可由反演直接算出精确值

$$\parallel {\mu }^{\ast t}-U{\parallel }_{\mathrm{TV}}=\frac{2}{3}{2}^{-t}(t\ge 1).$$

计算核验。 本期用 Python 的精确有理数枚举 $S_3$ 全部 $6$ 个状态，逐次卷积并核验了 $t=1,\dots ,8$。惰性游走的总变差依次符合 $\frac{2}{3}{2}^{-t}$，相对均匀分布的 ${\chi }^2$ 能量符合 $4\cdot 4^{-t}$；非惰性版本在同一范围内始终为总变差 $1/2$、${\chi }^2=1$。这是有限范围 sanity check，不替代理论推导。

1.6 Graduate / modern extension：块谱，而非单个“第二特征值”

对一般非中心增量，$\hat{\mu }(\pi )$ 不再是标量；真正的慢模态可能藏在某个高维不可约表示的某个方向中。若 $\mu$ 对称，每块 Hermitian，群上 Markov 算子的非平凡谱正是这些块的特征值按表示维数展开后的集合。若采用标准 lazy 化，即令停留概率至少为 $1/2$，则全部特征值被压到非负区间，spectral gap（谱隙）便直接控制 $L^2$ 衰减与 mixing time（混合时间）；仅有任意小的正停留概率虽足以打破周期，却未必使全部特征值非负。

Levin--Peres--Wilmer 的有限可逆链谱表示给出一般框架：absolute spectral gap（绝对谱隙）${\gamma }_{\ast }=1-\underset{\lambda \ne 1}{max}|\lambda |$ 控制方差以 $(1-{\gamma }_{\ast }{)}^{2t}$ 衰减，并给出含最小平稳质量的总变差混合上界。有限群 Fourier 理论的额外价值，是把一个 $N\times N$ 转移矩阵的谱问题按不可约表示拆成许多较小矩阵问题。

2. 固定模板习题 (Template Exercise)

题目

设 $(S_n{)}_{n\ge 0}$ 是状态空间 $\{0,1,\dots ,m\}$ 上的简单对称随机游走：在 $1\le i\le m-1$ 时，以概率 $1/2$ 移到 $i-1$ 或 $i+1$；到达 $0$ 或 $m$ 后吸收。令

$${\tau }_0:=inf\{n\ge 0:S_n=0\},{\tau }_m:=inf\{n\ge 0:S_n=m\},\tau :={\tau }_0\wedge {\tau }_m.$$

对每个起点 $i\in \{0,1,\dots ,m\}$，求并证明：

1. ${\mathbb{P}}_i({\tau }_m<{\tau }_0)$；
2. ${\mathbb{E}}_i\tau$。

模板识别

看到“最近邻 Markov 链 + 首次到达边界 + 命中概率或期望时长”，先按第一步分类。命中概率满足离散 harmonic equation（调和方程），期望时长因每走一步多出常数 $1$ 而满足 discrete Poisson equation（离散 Poisson 方程）；边界条件决定唯一解。

分级提示

1. Hint 1. 记 $p_i={\mathbb{P}}_i({\tau }_m<{\tau }_0)$。对 $1\le i\le m-1$，第一步后写出 $p_i$ 与 $p_{i-1},p_{i+1}$ 的关系，并写出 $p_0,p_m$。
2. Hint 2. 方程 $2p_i=p_{i-1}+p_{i+1}$ 说明一阶差分 $p_i-p_{i-1}$ 如何变化？
3. Hint 3. 记 $h_i={\mathbb{E}}_i\tau$。第一步分解中别漏掉已经耗费的那一步：$h_i=1+\frac{1}{2}{h}_{i-1}+\frac{1}{2}{h}_{i+1}$。
4. Hint 4. 检验二次函数 $q_i=i(m-i)$ 的边界值与二阶差分；再说明同一边值问题不可能有两个不同解。

3. 大家之言 (Mathematician in Their Own Words)

可核验语境。 2026 年 9 月 14 日，category theorist（范畴论学者）Emily Riehl 在 Terence Tao 的 What's new 博客发表客座文章 “Why I do mathematical research”。页面明确标注该文由 Riehl 撰写，并注明原稿从另一文件格式经 AI 转换。她谈到自己偏爱的数学研究目的时写道：

“Of the many purposes of mathematics, my favorite is to search for the simplest explanation of a particular phenomenon.”

中译。 “在数学的诸多目的中，我最偏爱的是：为某个特定现象寻找最简单的解释。”

评论。 这里的 “simplest” 不是把定理削成最短公式。Riehl 紧接着强调，常常需要发明一种澄清性的抽象语言，从纷杂细节中隔离共同模式，而且目标不是最大一般性，而是“恰当”的一般性。今天的表示块正是这种压缩：六状态、乃至 $|G|$ 状态的概率递推，被改写为不可约块的矩阵幂；中心性又准确说明何时还能进一步压成特征标比。抽象若没有保留周期障碍、块方向和假设边界，就不是解释，而只是删失。

4. 反例与边界 (Counterexample & Boundary)

支撑生成整个群，仍可能永不混合

删除“非周期”条件。仍取 $G=S_3$，但令增量测度为三个换位上的均匀分布

$$\nu =\mathrm{Unif}(T),$$

不再加入停留概率。逐项检查：

1. 不可约。 任意两个不同换位生成 $S_3$，故 $\mathrm{supp}\nu =T$ 生成整个群；游走不可约。
2. 对称且均匀分布平稳。 每个换位等于自身逆元，所以 $\nu (g)=\nu (g^{-1})$；有限群随机游走的均匀分布 $U$ 平稳。
3. 每一步翻转奇偶性。 换位是奇置换。从 $e$ 出发，偶数时刻必在 $A_3$，奇数时刻必在奇陪集中。
4. 分布在相应陪集内均匀。 $\nu$ 是中心测度；直接卷积可见，奇数时刻均匀分布在三个换位上，正偶数时刻均匀分布在 $A_3$ 上。
5. 总变差不衰减。 对每个 $t\ge 1$，令 $C_t$ 为时刻 $t$ 可达的奇偶陪集，则 ${\nu }^{\ast t}(C_t)=1$ 而 $U(C_t)=1/2$，故
   $$\parallel {\nu }^{\ast t}-U{\parallel }_{\mathrm{TV}}\ge \frac{1}{2}.$$
   两个分布在每个三元素陪集上的具体质量又给出反向等号，所以对所有 $t\ge 1$，该距离恰为 $1/2$。
6. Fourier 侧的障碍。 对符号表示，
   $$a_{\mathrm{sgn}}=\sum _g\nu (g)\mathrm{sgn}(g)=-1.$$
   它的 $t$ 次幂只在 $\pm 1$ 间振荡，模长从不变小。

故“支撑生成 $G$”只等价于不可约，不能推出逐时刻收敛。加入惰性后，该符号块从 $-1$ 变成 $0$，奇偶障碍被立即消除。边界不在特征值是否小于 $1$，而在所有非平凡特征值的模是否严格小于 $1$。

5. 今日一问与数学地图 (Question & Map)

今日一问。 设 $\mu$ 是有限群 $G$ 上的对称概率测度，满足 $\mu (e)>0$，且 $\mathrm{supp}\mu$ 生成 $G$。试证明：对每个非平凡不可约酉表示 $\pi$，都有

$$\parallel \hat{\mu }(\pi ){\parallel }_{\mathrm{op}}<1.$$

进一步把这一严格压缩代回上界引理，给出形如

$$\parallel {\mu }^{\ast t}-U{\parallel }_{\mathrm{TV}}\le C_G{\rho }^t,0\le \rho <1,$$

的显式选择，其中 $\rho$ 由全部非平凡表示块决定。为什么若删去 $\mu (e)>0$，$\rho$ 可能重新等于 $1$？

定向提示。 先用对称性说明 $\hat{\mu }(\pi )$ Hermitian 且算子范数不超过 $1$。若单位向量 $v$ 达到模长 $1$ 的极端值，分析三角不等式取等条件：支撑中的各个酉算子 $\pi (g)$ 必须怎样作用于 $v$？再利用单位元的正质量排除相位 $-1$，并用支撑生成性把结论传播到整个群。

数学地图。

$$\begin{array}{c}\text{有限群与独立群增量}\\ \Downarrow \\ {\mu }^{\ast t}\text{概率卷积幂}\\ \Downarrow \text{finite-group Fourier transform}\\ \widehat{{\mu }^{\ast t}}(\pi )=\hat{\mu }(\pi {)}^t\\ \Downarrow \text{Plancherel + Cauchy--Schwarz}\\ \text{非平凡表示块控制总变差混合}\\ \Downarrow \text{中心测度 / Schur 引理}\\ \text{character ratios 与显式谱}\\ \Downarrow \\ \text{Cayley 图谱隙、扩张与洗牌截止}\\ \Downarrow \\ \text{准随机群、非交换调和分析与快速采样}\end{array}$$

附录 A：习题完整解答 (Full Solution)

展开完整解答

可复用模板：首步分解 $\to$ 离散 Dirichlet/Poisson 边值问题 $\to$ 差分求解 $\to$ 最大值原理保证唯一。

先说明期望合法。无论当前位于哪个内点，在接下来的至多 $m$ 步里连续向同一方向走即可撞到某个边界，其概率至少为 $2^{-m}$。由 Markov 性，

$${\mathbb{P}}_i(\tau >km)\le (1-2^{-m}{)}^k,$$

故 $\tau <\mathrm{\infty }$ 几乎必然且 ${\mathbb{E}}_i\tau <\mathrm{\infty }$。

1. 先到达 $m$ 的概率

令

$$p_i:={\mathbb{P}}_i({\tau }_m<{\tau }_0).$$

边界条件为 $p_0=0$、$p_m=1$。对每个 $1\le i\le m-1$ 按第一步分类：

$$p_i=\frac{1}{2}{p}_{i-1}+\frac{1}{2}{p}_{i+1}.$$

因此

$$p_{i+1}-p_i=p_i-p_{i-1},$$

即一阶差分为常数，所以 $p_i=A+Bi$。代入两个边界条件得 $A=0$、$B=1/m$，从而

$$\boxed{{\displaystyle {\mathbb{P}}_i({\tau }_m<{\tau }_0)=\frac{i}{m}.}}$$

2. 吸收时间的期望

令 $h_i:={\mathbb{E}}_i\tau$。边界条件为 $h_0=h_m=0$。对内点按第一步分类，并计入已经走过的一步：

$$h_i=1+\frac{1}{2}{h}_{i-1}+\frac{1}{2}{h}_{i+1},$$

等价于

$$h_{i+1}-2h_i+h_{i-1}=-2.$$

检验 $q_i=i(m-i)$：它满足 $q_0=q_m=0$，且

$$q_{i+1}-2q_i+q_{i-1}=-2.$$

因此 $q$ 是候选解。为证明唯一性，若 $h$ 与 $\tilde{h}$ 都满足同一边值问题，则 $r=h-\tilde{h}$ 满足

$$r_0=r_m=0,r_i=\frac{1}{2}(r_{i-1}+r_{i+1}).$$

若 $r$ 有正的内点最大值，调和等式迫使相邻点也取得同一最大值，迭代至边界便与边界值 $0$ 矛盾；对 $-r$ 同理可排除负的内点最小值。因此 $r\equiv 0$。故

$$\boxed{{\displaystyle {\mathbb{E}}_i\tau =i(m-i).}}$$

同一模板可直接迁移到有偏随机游走：调和方程由算术差分改为几何差分，期望方程仍是带常数源项的离散 Poisson 方程。

资料与来源 (Sources)

1. David A. Levin, Yuval Peres, with contributions by Elizabeth L. Wilmer, Markov Chains and Mixing Times, 2nd ed., American Mathematical Society, 2017. 本期打开并核对了 §2.6 关于群上随机游走、均匀平稳分布、支撑生成与可逆性的命题，以及 Chapter 12 关于可逆转移矩阵谱表示、绝对谱隙、方差衰减和混合时间界的论述：https://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf
2. Pavel Etingof, Oleg Golberg, Sebastian Hensel, Tiankai Liu, Alex Schwendner, Dmitry Vaintrob, and Elena Yudovina, Introduction to Representation Theory, lecture notes dated 2011-01-10. 本期打开并核对了 §3.1 的正则表示维数平方分解、§3.5 的特征标正交与 §3.7 的矩阵系数正交；它们是 Plancherel 块分解与中心测度标量化的表示论基础：https://math.mit.edu/~etingof/replect.pdf
3. Emily Riehl, “Why I do mathematical research,” guest post on Terence Tao's What's new, 2026-09-14. 第 3 节引文已按原页面逐字核对；页面同时披露了作者身份及文件格式转换说明：https://terrytao.wordpress.com/2026/09/14/why-i-do-mathematical-research