随机变量之和的模分布与离散 Fourier 变换

下面是一道中科大 2026 年入学考试的数学题的推广。

Problem

任取正整数 $m$ ，假设 $n$ 个随机变量 $X_1,\dots,X_n$ 独立同分布，满足

Copy LaTeX

求

Copy LaTeX

一种最标准和简单无脑的解法是利用状态转移关系和线性代数方法去处理，问题最终需要通过离散 Fourier 变换求解。这个问题还可以解释为 $\mathbb{Z}_m$ 上的随机游走。

Solution

记

Copy LaTeX

那么可以得到状态转移关系

Copy LaTeX

以及初始状态

Copy LaTeX

由此可知，对于 $k \in \{0,1,\dots,m-1\}$ ，有如下关系

Copy LaTeX

因此问题归结于计算循环矩阵 $\boldsymbol{S}$ 的 $n$ 次方 $\boldsymbol{S}^n$ 的第一列的所有元素。

易得 $\boldsymbol{S}^n$ 仍然是循环矩阵，可以用离散 Fourier 矩阵进行对角化，离散 Fourier 矩阵记作

Copy LaTeX

其中 $w = e^{2\pi i/m}$ 是 $m$ 次单位根。那么 $\boldsymbol{S}^n$ 可以表示为

Copy LaTeX

其中 $f$ 是多项式

Copy LaTeX

因此

Copy LaTeX

Example

在上述问题中，考虑一个更具体的例子：取 $m=3$ ， $n=2026$

Copy LaTeX

求

Copy LaTeX

Solution

代入可得

Copy LaTeX

以及

Copy LaTeX

得到

Copy LaTeX

因此对于 $k=0$ 有

Copy LaTeX

对这个小规模的具体问题，我们也可以完全把矩阵分解的实质隐藏起来，直接用二阶线性递推数列去求解。

Solution

记 $S_n = \sum_{i=1}^n X_i$ ，引入

Copy LaTeX

可以得到

Copy LaTeX

可以归一化条件 $u_n + v_n + w_n = 1$ 消去 $w_n$

Copy LaTeX

得到二阶递推关系

Copy LaTeX

引入变量代换偏移以消除常数

Copy LaTeX

得到

Copy LaTeX

这个数列有规律

Copy LaTeX

由于 $2026 = 6 \times 337 + 4$ ，因此只需要计算

Copy LaTeX

因此

Copy LaTeX

得到结果

Copy LaTeX

这个问题其实还有一种基于单位根滤子（roots-of-unity filter）的解法，这是算法或组合概率中的一个标准技巧，实质上就是离散 Fourier 变换的一种具体应用。

单位根滤子是如下结构：

Copy LaTeX

其中 $w = e^{2\pi i/m}$ 是 $m$ 次单位根。这个关系其实就是离散 Fourier 矩阵的任意两行或两列相互正交。不妨改为如下写法

Copy LaTeX

对于随机变量 $S$ ，考虑概率

Copy LaTeX

可以将其转换为 $\mathbf{1}_{\{m \mid S\}}$ 的数学期望

Copy LaTeX

Solution (基于单位根滤子的解法)

取 $m=3$ ， $w = e^{2\pi i/3}$ 是 $3$ 次单位根，对应的单位根滤子为

Copy LaTeX

那么

Copy LaTeX

记

Copy LaTeX

由于 $X_i$ 独立同分布，可以得到

Copy LaTeX

其中的单个 $X$ 对应的 $w^X$ 和 $w^{2X}$ 的期望为

Copy LaTeX

因此

Copy LaTeX

剩下的具体计算与前面的解法相同，这里略去。

还可以用所谓的单位根反演的技巧进行求解，实际上和单位根滤子一样，仍然是离散 Fourier 变换和逆变换的具体应用。

我们关注一个序列 $\{a_k,\,k \geqslant 0\}$ ，对其按照下标模 $m$ 进行分类求和

Copy LaTeX

引入幂级数

Copy LaTeX

利用 $m$ 次单位根 $w = e^{2\pi i/m}$ 满足的性质

Copy LaTeX

可以得到

Copy LaTeX

这实际上就是一个离散 Fourier 变换（系数取 $1$ ，对应的逆变换系数取 $\frac{1}{m}$ ）

Copy LaTeX

那么显然有如下离散 Fourier 逆变换

Copy LaTeX

这也被称为单位根反演。

上述过程可以用于概率的求解（对应的是概率生成函数方法）：考虑取值为非负整数的随机变量 $S$ ，其概率生成函数为

Copy LaTeX

记系数

Copy LaTeX

得到

Copy LaTeX

因此可以用单位根反演公式得到

Copy LaTeX

Solution (基于单位根反演的解法)

取 $m=3$ ， $w = e^{2\pi i/3}$ 是 $3$ 次单位根，记 $a_k = P(S = k)$ ，那么

Copy LaTeX

以及

Copy LaTeX

由推导可知这两组数据存在离散 Fourier 变换 / 逆变换的转换关系。因此，利用单位根反演公式可得

Copy LaTeX

剩下的过程和前一种解法相同。

Remark

从概率论的角度来说，这里使用了生成函数的技巧（实质是卷积、离散 Fourier 变换），把随机变量之和的问题转换为了随机变量乘积的问题，后者显然更好处理。

这道题其实还可以直接从二项式分组求和的表达式去入手。

Solution (二项式分组求和)

要求

Copy LaTeX

整除 $3$ ，其中 $X_i$ 为 $1$ 或 $2$ 。不妨设其中 $k$ 个为 $2$ ， $2026-k$ 个为 $1$ ，那么

Copy LaTeX

因此需要

Copy LaTeX

直接得到如下求和

Copy LaTeX

这个表达式很容易就写出来，但是问题是不好给出显式的结果。

考虑构造辅助函数

Copy LaTeX

我们关注系数对指标模 $3$ 进行的分组求和（目标是求出 $P(3 \mid S) = A_2$ 的值）

Copy LaTeX

取 $x = w = e^{2\pi i/3}$ 为 $3$ 次单位根，在 $1,w,w^2$ 求值就可以自然地对系数分组，计算可得

Copy LaTeX

这里又自然得到了离散 Fourier 变换公式。当然我们可以将其看作一个普通的三元一次线性方程组，直接解出 $A_0,A_1,A_2$ ，因此

Copy LaTeX

剩下的过程和前面的解法一致，这里不再重复。

Remark

这个一般问题的实质是模 $m$ 的分类问题，无论采用什么思路，最终都会自然汇合到 $\mathbb{Z}_m$ 上的 Fourier 分析，也就是离散 Fourier 变换。在最一般的基于循环矩阵的线性代数方法中，单位根作为循环矩阵的特征值和特征向量结构自然出现。相比之下，在单位根滤子、单位根反演以及二项式分组求和中，代入单位根的操作往往显得具有较强的技巧性。