星差异与低差异序列

形式陈述 ​

给定单位立方 $[0,1{)}^d$ 中的 $N$ 个点 $P_N=\{x_1,\dots ,x_N\}$，其中允许点按重数计数。对 $t=(t_1,\dots ,t_d)\in [0,1{]}^d$，定义锚定盒

$$[0,t)=\prod _{j=1}^d[0,t_j)$$

和经验计数

$$A_N([0,t))=\mathrm{\#}\{1\le n\le N:x_n\in [0,t)\}.$$

$P_N$ 的星差异为

$$D_N^{\ast }(P_N)=\underset{t\in [0,1{]}^d}{sup}|\frac{A_N([0,t))}{N}-\prod _{j=1}^d{t}_j|.$$

第二项是均匀分布公理库均匀分布Uniform distribution在有限集合或有限正测度区域上按计数或体积等比例分配概率的分布。赋予该盒的体积。星差异因此比较经验测度 $N^{-1}\sum _{n=1}^N{\delta }_{x_n}$ 与均匀测度在所有原点锚定盒上的最大偏差。

对无限点列公理库序列Sequence以自然数为定义域的函数。 $(x_n{)}_{n\ge 1}\subset [0,1{)}^d$，若其前 $N$ 项星差异满足

$$D_N^{\ast }=O\left(\frac{(\log N{)}^d}{N}\right),$$

常称其为低差异序列。不同文献对对数指数采用略有差别的约定；不依赖具体速率的基本要求是 $D_N^{\ast }\to 0$，这等价于点列对所有轴对齐盒均匀分布。术语“低差异”描述的是随 $N$ 的确定性覆盖质量，而不是某个固定阈值。

直觉 ​

每个锚定盒提出一个简单问题：前 $N$ 个点落进来的比例，是否接近盒子占单位立方的体积？星差异把所有这类问题中最坏的一个留下。点云即使肉眼看起来分散，只要在某个角落系统性缺点，就会被相应的锚定盒检出。

只测试锚定盒仍足以控制一般轴对齐盒，因为 $(a,b]$ 的指标函数可用至多 $2^d$ 个锚定盒指标按容斥展开。不过常数随维数增长，这已经提示“在低维很均匀”不能无代价地外推到高维。

例子与计算 ​

一维时，把点排序为 $0\le x_{(1)}\le \cdots \le x_{(N)}<1$。星差异可精确写成

$$D_N^{\ast }=\underset{1\le i\le N}{max}\{\frac{i}{N}-x_{(i)},x_{(i)}-\frac{i-1}{N}\}.$$

取中点集 $x_i=(i-1/2)/N$。在相邻两点之间，经验分布函数保持常数，而均匀分布函数线性增长；最大偏差恰为

$$D_N^{\ast }=\frac{1}{2N}.$$

这给出一个具体正例：每个点居于等长小区间中心，最坏累计偏差只有半个区间的质量。

相比之下，若 $N$ 个点全部等于 $1/2$，对 $t$ 从 $1/2$ 左侧逼近时经验比例为零而体积趋近 $1/2$；越过 $1/2$ 后经验比例跳到一，因此 $D_N^{\ast }=1/2$。点的重数会真实影响经验分布，不能把重复点自动去重。

二维中，规则 $m\times m$ 网格的 $N=m^2$ 个单元中心具有量级 $N^{-1/2}$ 的边界误差，因为盒的上边和右边最多切过 $O(m)$ 个网格单元。低差异构造试图把这种维数造成的网格损失改进为接近 $N^{-1}$ 的对数修正。

边界与失败情形 ​

星差异不是随机误差方差。对独立均匀样本，$A_N([0,t))/N$ 是随机变量，固定盒上的方差为 $v(1-v)/N$；$D_N^{\ast }$ 则是同时对所有盒取上确界后的随机量。确定性低差异点列甚至没有抽样方差，除非另外引入随机平移或 scrambling。

它也不是所有函数积分误差的精确值。Koksma–Hlawka 不等式在 $f$ 具有有限 Hardy–Krause 变差时给出

$$|\frac{1}{N}\sum _{n=1}^{N}f(x_n)-{\int }_{[0,1{]}^d}f(x)dx|\le V_{HK}(f)D_N^{\ast }.$$

若 $V_{HK}(f)=\mathrm{\infty }$，右侧没有有效含义；小星差异不会单独保证每个不连续或高度振荡被积函数都有小误差。

边界约定必须一致。使用 $[0,1{)}^d$ 与半开盒避免点恰落在分割面时重复计数；改成闭盒会在有限点集上改变极值位置，虽然渐近结论通常不受影响。星差异还依赖坐标轴，旋转点集后可能改变，故它不等同于旋转不变的几何均匀性。

推论与应用 ​

Weyl 判别法把 $D_N^{\ast }\to 0$ 与点列对连续函数的经验平均收敛到均匀积分联系起来。星差异给出一个有限样本、可量化的版本：它直接控制盒指标，并在附加变差条件下控制更广的被积函数。

Halton、Sobol 与数字网格等构造利用不同进制的分层结构，力求让每个尺度的盒都获得接近应有数量的点。拟 Monte Carlo 积分使用这些点列代替独立样本；实际优势取决于维数、坐标权重、被积函数正则性和随机化方式，不能只凭“低差异”标签保证。

参考资料

• Harald Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, SIAM, 1992，Ch. 2–4。
• Josef Dick and Friedrich Pillichshammer, Digital Nets and Sequences, Cambridge University Press, 2010，Ch. 2–3。
• Michael Drmota and Robert F. Tichy, Sequences, Discrepancies and Applications, Springer, 1997，Ch. 1。