Halton序列均匀产生多维随机数的介绍与实现

Halton序列

在统计学中，Halton序列是用于生成空间中的点的序列，如Monte Carlo模拟的数值方法，虽然这些序列是确定性的，但它们的差异性很低，也就是说，在许多方面看起来是随机的。它们在1960年首次提出，是准随机数列的一个例子。它们概括了一维Van der Corput序列

用于生成R2R2中(0,1)x(0,1)点的Halton序列的例子

Halton数列是以质数为基的确定性方法构造的。举个简单的例子，让我们把Halton序列的一个维度基于2，另一个基于3。为了生成2的序列，我们首先将区间(0,1)(0,1)分成两半，然后分成四分之一、八分之一等，这就产生了

12,14,34,18,58,38,78,116,916...12,14,34,18,58,38,78,116,916...

等价的，这个序列的第n个数字是用二进制表示的数字n，倒过来，并写在小数点之后。这对任何基数都是如此。举个例子，要找到上述序列的第六个元素，我们要写6=1∗22+1∗21+0∗20=11026=1∗22+1∗21+0∗20=1102，可以倒置并放在小数点之后，得到0.0112=0∗2−1+1∗2−2+1∗2−3=380.0112=0∗2−1+1∗2−2+1∗2−3=38。所以上面的序列与0.12,0.012,0.112,0.0012,0.1012,0.0112,0.1112,0.00012,0.100120.12,0.012,0.112,0.0012,0.1012,0.0112,0.1112,0.00012,0.10012相同 为了生成3的序列，我们把区间(0,1)(0,1)分成三份，然后是九份，二十七份，等等...这就产生了（同理表示成三进制的数，然后进行相应操作）

13,23,19,49,79,29,59,89,127,...13,23,19,49,79,29,59,89,127,...

当我们把它们配对起来时，我们会得到一个单位方格中的点的序列。

(12,13),(14,23),(34,19),(18,49),(58,79),(38,29),(78,59),(116,89),(916,127).(12,13),(14,23),(34,19),(18,49),(58,79),(38,29),(78,59),(116,89),(916,127).

尽管标准的Halton序列在低维情况下表现的很好，但由高质数生成的序列之间存在相关问题。例如，如果我们从质数17和19开始，前16个对点数:(117,119),(217,219),(317,319)...(1617,1619)(117,119),(217,219),(317,319)...(1617,1619)具有完美的线性相关性。为了避免这种情况，通常会删除前20个条目，或者根据选择的指数来删除其他预定的数量。还提出了其他几种办法，最突出的解决方案之一是scrambled Halton序列，它使用在构建标准序列中使用的系数的排列组合。另一个解决方案是leaped Halton，它会在标准序列中跳过点(例如，只有每409个点(也可以是其他没有在Halton核心序列中使用的质数)，才能取得显著的改进)。

实现

伪代码

复制代码1234567891011121314CPPalgorithm Halton-Sequence is
	inputs: index i
			base b
	output: result r

	f⬅1
	r⬅0

	while i > 0 do
		f⬅f/b
		r⬅r+f * (i mod b)
		i⬅[i/b]
	
	return r

下面的生成器函数 generator function （Python）中给出了另一种实现方式，它可以产生以bb为基数的Halton序列的后续数字。这种算法在内部只使用整数，这使得它对四舍五入的错误具有很强的健壮性。

复制代码1234567891011121314PYTHONdef halton(b):
    """Generator function for Halton sequence."""
    n, d = 0, 1
    while True:
        x = d - n
        if x == 1:
            n = 1
            d *= b
        else:
            y = d // b
            while x <= y:
                y //= b
            n = (b + 1) * y - x
        yield n / d