专栏首页阿林前端开发攻城狮Halton序列均匀产生多维随机数的介绍与实现
原创

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

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Hammersley序列的对比实现伪代码

    Halton序列无需在生成随机数之前,知道需要生成随机点的个数,但是在用一些比较大的质数作为底数时,Halton序列的分布在点的数量不那么多的时候并不会均匀的分...

    用户7108768
  • Scrambled后的序列依然具有radical inversion的性质

    原文中陈述了很多具体的例子,而缺乏了一些Halton序列本身的说明,使用场景、以及与其他序列使用对比的差异,故在此处进行补充

    用户7108768
  • 蒙特卡洛算法及其实现

    从今天开始要研究Sampling Methods,主要是MCMC算法。本文是开篇文章,先来了解蒙特卡洛算法。 Contents    1. 蒙特卡洛介绍    ...

    Angel_Kitty
  • 伪蒙特卡洛(Quasi-Monte Carlo, QMC)随机

    分享一道由群员“Melbourne”,外号 “Paper Machine”,有数学小王子之称的小伙伴分享的题目!

    程序员小浩
  • python数据科学系列:numpy入门详细教程

    python数据科学基础库主要是三剑客:numpy,pandas以及matplotlib,每个库都集成了大量的方法接口,配合使用功能强大。平时虽然一直在用,也看...

    luanhz
  • 【笔记】《计算机图形学》(14)——采样

    本章的用意在于为未来更深一步的光线追踪探索(第23章介绍路径追踪,第24章介绍反射模型)打下数学基础,介绍了计算机中常用的采样和积分理论,且核心是采样方法。内容...

    ZifengHuang
  • [MCSM]伪随机数和伪随机数生成器

    http://en.wikipedia.org/wiki/Monte_Carlo_method

    sea-wind
  • 金融工程高度概览

    整个流程图分为 6 大模块,除了开始的“数据参数”模块,后 5 个模块都有相对应的函数。

    用户5753894
  • 基于sklearn的LogisticRegression二分类实践

    本文使用sklearn的逻辑斯谛回归模型,进行二分类预测,并通过调整各种参数,对预测结果进行对比。

    Michael阿明
  • 【深度干货】专知主题链路知识推荐#5-机器学习中似懂非懂的马尔科夫链蒙特卡洛采样(MCMC)入门教程01

    【导读】主题链路知识是我们专知的核心功能之一,为用户提供AI领域系统性的知识学习服务,一站式学习人工智能的知识,包含人工智能( 机器学习、自然语言处理、计算机视...

    WZEARW
  • Data Science | Numpy基础(二)

    按照上篇文章,相信大家都安装好了Anaconda,有朋友在留言区留言希望出一篇关于Anaconda的使用教程,其实Anaconda的基本使用非常简单,基本无需教...

    咸鱼学Python
  • Nat. Methods | 利用深度学习进行基于生物物理学和数据驱动的分子机制建模

    本文介绍由美国马萨诸塞州波士顿哈佛医学院系统生物学系系统药理学实验室的Mohammed AlQuraishi等人发表于Nature Methods 的研究成果:...

    DrugAI
  • 数据分析师最爱的脚本语言--Python,你会了吗?

    据各种专业和业余的统计,在机器学习领域,Python语言的热度逐年上升。作为一种计算机程序设计语言,以简洁,易读性被广泛选择。伴随着大数据,深度学习领域的迅速发...

    用户8612862
  • Coursera吴恩达《优化深度神经网络》课程笔记(3)-- 超参数调试、Batch正则化和编程框架

    上节课我们主要介绍了深度神经网络的优化算法。包括对原始数据集进行分割,使用mini-batch gradient descent。然后介绍了指数加权平均(Exp...

    红色石头
  • 粒子滤波到底是怎么得到的?

    粒子滤波(particle filter)是一种常见的滤波算法,广泛应用于目标跟踪、移动机器人等领域。网络上有不少关于粒子滤波的资料,但大多是直接给出了粒子滤波...

    计算机视觉
  • C++ 实现银行排队服务模拟

    教程简介:使用 C++对银行排队服务进行模拟,以事件驱动为核心思想,手动实现模板链式队列、随机数产生器等内容,进而学习概率编程等知识。作为可选进阶,这个模型同时...

    李海彬
  • C++ 实现银行排队服务模拟

    教程简介:使用 C++对银行排队服务进行模拟,以事件驱动为核心思想,手动实现模板链式队列、随机数产生器等内容,进而学习概率编程等知识。作为可选进阶,这个模型同时...

    李海彬
  • TiDB 源码阅读系列文章(十二)统计信息(上)

    在 TiDB 里,SQL 优化的过程可以分为逻辑优化和物理优化两个部分,在物理优化阶段需要为逻辑查询计划中的算子估算运行代价,并选择其中代价最低的一条查询路径作...

    PingCAP
  • 【Excel系列】Excel数据分析:抽样设计

    一、随机数发生器 1. 随机数发生器主要功能 “随机数发生器”分析工具可用几个分布之一产生的独立随机数来填充某个区域。可以通过概率分布来表示总体中的主体特征。...

    数据科学社区

扫码关注云+社区

领取腾讯云代金券